Patterns

Implement a sorting algorithm from scratch (bubble, insertion, selection, merge, quick)

When to useDrilling the mechanics of sorting algorithms; understanding time/space tradeoffs

iterative

INITIALIZE

n = arr.length; any pass-tracking flags

const result = [...arr];
const n = result.length;

const result = [...arr];
const n = result.length;

const result = [...arr]; const n = result.length;

const a = [...arr]; let swaps = 0; const n = a.length;

const result = [...arr]; let comparisons = 0;

—

const result = [...unsortedList];
const n = result.length;

—

TRAVERSE

outer pass over array (n-1 passes typical)

for (let i = 0; i < n - 1; i++) {

for (let i = 1; i < n; i++) {

for (let i = 0; i < n - 1; i++) {

for (let i = 0; i < n - 1; i++) {

for (let i = 1; i < result.length; i++) {

—

for (let i = 1; i < n; i++) {

—

inner pass

inner loop to compare/swap or select

  let minIndex = i;
  for (let j = i + 1; j < n; j++) {

  while (j >= 0 && result[j] > current) {

  let swapped = false;
  for (let j = 0; j < n - 1 - i; j++) {

  for (let j = 0; j < n - 1 - i; j++) {

  const current = result[i]; let j = i - 1;
  while (j >= 0) { comparisons++;

—

  while (j >= 0 && result[j] > key) {

—

[COMPARE-SWAP]

conditional swap or merge step

    if (result[j] < result[minIndex]) minIndex = j;

    result[j + 1] = result[j]; j--;

    if (result[j] > result[j + 1]) {
      const tmp = result[j]; result[j] = result[j+1]; result[j+1] = tmp;
      swapped = true;
    }

    if (a[j] > a[j + 1]) {
      [a[j], a[j + 1]] = [a[j + 1], a[j]];
      swaps++;
    }

    if (result[j] > current) { result[j + 1] = result[j]; j--; }
    else break;

return merge(sortedLeft, sortedRight);
// merge: two-pointer walk, push smaller, drain remainders

    result[j + 1] = result[j]; j--;

// in-place — no merge needed; pivot is in final position

RETURN

return sorted array (in place or new)

return result;

return result;

return result;

return swaps;

return { sorted: result, comparisons };

—

return result;

—