Learn Data Structures & Algorithms in 10 DaysDay 6: Sorting Algorithms
books.chapter 6Learn Data Structures & Algorithms in 10 Days

Day 6: Sorting Algorithms

What You'll Learn Today

  • Basic sorts: Bubble Sort, Selection Sort, Insertion Sort
  • Efficient sorts: Merge Sort, Quick Sort
  • Characteristics and tradeoffs of each
  • JavaScript's built-in sort

Sorting Algorithm Categories

flowchart TB
    subgraph Basic["Basic Sorts O(nĀ²)"]
        BS["Bubble Sort"]
        SS["Selection Sort"]
        IS["Insertion Sort"]
    end
    subgraph Efficient["Efficient Sorts O(n log n)"]
        MS["Merge Sort"]
        QS["Quick Sort"]
    end
    style Basic fill:#f59e0b,color:#fff
    style Efficient fill:#22c55e,color:#fff

Bubble Sort

Repeatedly compares adjacent elements and swaps them if out of order. The largest values "bubble" to the end.

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    let swapped = false;
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return arr;
}

console.log(bubbleSort([64, 34, 25, 12, 22, 11, 90]));
// [11, 12, 22, 25, 34, 64, 90]
Property Value
Best O(n) when already sorted
Average O(nĀ²)
Worst O(nĀ²)
Space O(1)
Stable Yes

Selection Sort

Finds the minimum in the unsorted portion and places it at the front.

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}
Property Value
Best O(nĀ²)
Average O(nĀ²)
Worst O(nĀ²)
Space O(1)
Stable No

Insertion Sort

Like sorting cards in your hand ā€” inserts each element into its correct position.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}
Property Value
Best O(n) when already sorted
Average O(nĀ²)
Worst O(nĀ²)
Space O(1)
Stable Yes

Insertion sort is highly efficient for small arrays or nearly sorted data.

Merge Sort

Uses divide and conquer: split the array in half, sort each half, then merge.

flowchart TB
    A["[38, 27, 43, 3]"] --> B["[38, 27]"]
    A --> C["[43, 3]"]
    B --> D["[38]"]
    B --> E["[27]"]
    C --> F["[43]"]
    C --> G["[3]"]
    D -.-> H["[27, 38]"]
    E -.-> H
    F -.-> I["[3, 43]"]
    G -.-> I
    H -.-> J["[3, 27, 38, 43]"]
    I -.-> J
    style A fill:#3b82f6,color:#fff
    style J fill:#22c55e,color:#fff

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}
Property Value
Best O(n log n)
Average O(n log n)
Worst O(n log n)
Space O(n)
Stable Yes

Quick Sort

Picks a pivot, then partitions elements into smaller-than-pivot (left) and larger-than-pivot (right).

flowchart TB
    A["[8, 3, 1, 7, 0, 10, 2]"] --> P["Pivot: 7"]
    P --> L["Left: [3, 1, 0, 2]"]
    P --> R["Right: [8, 10]"]
    L --> L2["[0, 1, 2, 3]"]
    R --> R2["[8, 10]"]
    L2 --> RESULT["[0, 1, 2, 3, 7, 8, 10]"]
    R2 --> RESULT
    style P fill:#f59e0b,color:#fff
    style L fill:#3b82f6,color:#fff
    style R fill:#ef4444,color:#fff
    style RESULT fill:#22c55e,color:#fff

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

In-Place Quick Sort

function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSortInPlace(arr, low, pivotIndex - 1);
    quickSortInPlace(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}
Property Value
Best O(n log n)
Average O(n log n)
Worst O(nĀ²) when already sorted with edge pivot
Space O(log n)
Stable No

Comparison

Algorithm Best Average Worst Space Stable
Bubble Sort O(n) O(nĀ²) O(nĀ²) O(1) Yes
Selection Sort O(nĀ²) O(nĀ²) O(nĀ²) O(1) No
Insertion Sort O(n) O(nĀ²) O(nĀ²) O(1) Yes
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quick Sort O(n log n) O(n log n) O(nĀ²) O(log n) No

Stability in Sorting

A stable sort preserves the relative order of elements with equal keys.

const students = [
  { name: "Alice", grade: "B" },
  { name: "Bob", grade: "A" },
  { name: "Charlie", grade: "B" },
  { name: "Diana", grade: "A" },
];

// Stable sort by grade:
// A: Bob, Diana (original order preserved)
// B: Alice, Charlie (original order preserved)

JavaScript's Array.sort()

// Default: lexicographic string comparison
[10, 9, 8, 1, 2, 3].sort();
// [1, 10, 2, 3, 8, 9] ā€” NOT numerical!

// Numerical sort with comparator
[10, 9, 8, 1, 2, 3].sort((a, b) => a - b);
// [1, 2, 3, 8, 9, 10]

// Sort objects
const people = [
  { name: "Charlie", age: 30 },
  { name: "Alice", age: 25 },
  { name: "Bob", age: 35 },
];
people.sort((a, b) => a.age - b.age);

JavaScript's Array.sort() is guaranteed to be stable (since ECMAScript 2019). Most engines use TimSort (a hybrid of Merge Sort and Insertion Sort).

Choosing the Right Sort

flowchart TB
    Q1{"Data size?"}
    Q1 -->|"Small (< 50)"| IS["Insertion Sort"]
    Q1 -->|"Large"| Q2{"Memory constrained?"}
    Q2 -->|"Yes"| QS["Quick Sort"]
    Q2 -->|"No"| Q3{"Need stability?"}
    Q3 -->|"Yes"| MS["Merge Sort"]
    Q3 -->|"No"| QS
    style IS fill:#22c55e,color:#fff
    style QS fill:#3b82f6,color:#fff
    style MS fill:#8b5cf6,color:#fff

Summary

Concept Description
Bubble Sort Swap adjacent elements; educational
Selection Sort Select minimum and place
Insertion Sort Efficient for small data
Merge Sort Stable, always O(n log n)
Quick Sort Fastest in practice, space-efficient

Key Takeaways

  1. Insertion sort is practical for small datasets
  2. Merge sort is stable and always O(n log n) but needs O(n) extra space
  3. Quick sort is the fastest on average but has O(nĀ²) worst case
  4. JavaScript's Array.sort() is stable

Practice Problems

Problem 1: Basic

Sort an array so that even numbers come before odd numbers (order within each group doesn't matter).

Problem 2: Intermediate

Sort an array of strings by length. If lengths are equal, sort alphabetically.

Challenge

Use merge sort to count the number of "inversions" in an array (pairs where i < j but arr[i] > arr[j]).

References

Next up: In Day 7, we'll explore "Trees & Binary Search Trees" ā€” managing hierarchical data efficiently.