Unsorted: [64, 25, 12, 22, 11]
Sorted:   [11, 12, 22, 25, 64]

flowchart LR
    subgraph Input[Original — sorted by name]
        I1["(Alice, 3)"] --> I2["(Bob, 1)"]
        I2 --> I3["(Carol, 3)"]
        I3 --> I4["(Dave, 2)"]
    end

    subgraph Stable[Stable — sort by score ✅]
        S1["(Bob, 1)"] --> S2["(Dave, 2)"]
        S2 --> S3["(Alice, 3) ← original order preserved"]
        S3 --> S4["(Carol, 3)"]
    end

    subgraph Unstable[Unstable — sort by score ❌]
        U1["(Bob, 1)"] --> U2["(Dave, 2)"]
        U2 --> U3["(Carol, 3) ← order flipped!"]
        U3 --> U4["(Alice, 3)"]
    end

    Input --> Stable
    Input --> Unstable

    style Input fill:#7c3aed,color:#fff
    style Stable fill:#059669,color:#fff
    style Unstable fill:#ef4444,color:#fff

Scenario: Sort employees first by department, then by salary within department.

Step 1: Sort by salary (any sort)      → [(Eve,$50k), (Bob,$60k), (Alice,$70k), (Carol,$80k)]
Step 2: Sort by department (STABLE)    → [(Alice,$70k), (Carol,$80k), (Bob,$60k), (Eve,$50k)]
                                               ↑ Engineering ↑         ↑ Sales ↑
                                        Within Engineering: $70k then $80k ✅ (salary order preserved)

// In-place: only using a few variables for swapping
function swap(arr, i, j) {
    let temp = arr[i];  // O(1) extra space
    arr[i] = arr[j];
    arr[j] = temp;
}

// Out-of-place: creates new arrays for left and right halves
function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));   // new array
    const right = mergeSort(arr.slice(mid));      // new array
    return merge(left, right);                    // new array
}

Is arr[i] > arr[j] ?  → Yes → swap them
                       → No  → leave them

Counting Sort: Count frequency of each value, then reconstruct
Radix Sort:    Sort digit by digit (from least to most significant)
Bucket Sort:   Distribute into buckets, sort each bucket

flowchart TB
    Sorts[Sorting Algorithms] --> Simple[Simple — O(n²)
Quadratic]
    Sorts --> Efficient[Efficient — O(n log n)
Linearithmic]
    Sorts --> Linear[Linear — O(n)
Non-Comparison]

    Simple --> Bubble[Bubble Sort
Stable, In-place]
    Simple --> Selection[Selection Sort
Unstable, In-place]
    Simple --> Insertion[Insertion Sort
Stable, In-place]

    Efficient --> Merge[Merge Sort
Stable, Out-of-place]
    Efficient --> Quick[Quick Sort
Unstable, In-place*]
    Efficient --> Heap[Heap Sort
Unstable, In-place]

    Linear --> Counting[Counting Sort
Stable, Out-of-place]
    Linear --> Radix[Radix Sort
Stable, Out-of-place]
    Linear --> Bucket[Bucket Sort
Stable, Out-of-place]

    style Sorts fill:#7c3aed,color:#fff
    style Simple fill:#f59e0b,color:#fff
    style Efficient fill:#059669,color:#fff
    style Linear fill:#3b82f6,color:#fff

flowchart TB
    Q1{Input size n?} -->|n smaller than 20| Ins1[Insertion Sort
Low overhead, fast]
    Q1 -->|n at least 20| Q2{Data nearly<br/>sorted?}
    Q2 -->|Yes| Ins2[Insertion Sort
O(n) best case]
    Q2 -->|No| Q3{Need stable?}
    Q3 -->|Yes| Q4{Memory OK?}
    Q4 -->|Yes ✅| Merge1[Merge Sort
Guaranteed O(n log n)]
    Q4 -->|No ❌| NoOpt[(No O(1) space<br/>stable sort exists)]
    Q3 -->|No| Q5{Memory<br/>constrained?}
    Q5 -->|Yes| Heap1[Heap Sort
O(n log n), O(1) space]
    Q5 -->|No| Q6{Worst-case<br/>critical?}
    Q6 -->|Yes| Merge2[Merge or Heap Sort]
    Q6 -->|No| Quick1[Quick Sort
Fastest in practice]

    style Q1 fill:#7c3aed,color:#fff
    style Q2 fill:#3b82f6,color:#fff
    style Q3 fill:#f59e0b,color:#fff
    style Q5 fill:#ec4899,color:#fff
    style Q6 fill:#06b6d4,color:#fff