06-Sorting-Merge-Quick

Buổi 06 — Sorting: Merge Sort & Quick Sort

Navigation

← 05-Binary-Search | → 07-Hash-Table Giai đoạn: Big Tech Foundation | Độ khó: ⭐⭐⭐

---

1. Analogy & Context

Merge Sort — Chia để trị xấp giấy tờ

Bàn làm việc bừa bộn

Bạn có một đống giấy tờ lộn xộn cần sắp xếp theo ngày. Thay vì sắp xếp cả đống một lúc, bạn chia làm hai, đưa cho hai đồng nghiệp xử lý riêng. Mỗi người lại chia tiếp cho hai người khác… Khi mọi người có đúng 1 tờ (đã “sorted”), bạn gộp lại từng cặp: so sánh tờ trên cùng của hai chồng, lấy tờ nhỏ hơn, lặp lại cho đến hết.

Kết quả: mỗi bước gộp chỉ cần so sánh đầu hai chồng → $O(N)$ mỗi level, $\log N$ levels → $O(N\log N)$.

Quick Sort — Sắp xếp chiều cao tại buổi tiệc

Trò chơi nhóm

Chọn một người làm pivot (chốt). Mọi người thấp hơn đứng sang trái, cao hơn đứng sang phải. Bây giờ lặp lại trong mỗi nhóm con: chọn pivot mới, chia tiếp. Không cần thêm không gian — mọi thứ xảy ra ngay tại chỗ.

Kết quả: trung bình mỗi pivot chia đôi nhóm → $O(N\log N)$ trung bình. Nhưng nếu luôn chọn min/max làm pivot → $O(N^2)$ worst case!

Điểm khác biệt cốt lõi:

	Merge Sort	Quick Sort
Approach	Chia trước, xử lý sau (post-order)	Xử lý trước, chia sau (pre-order)
Space	$O(N)$ auxiliary array	$O(\log N)$ stack (in-place)
Stability	Stable ✓	Unstable ✗
Worst case	$O(N\log N)$ — guaranteed	$O(N^2)$ — sorted input
Cache	Cache-unfriendly (merge step)	Cache-friendly (locality)

---

2. The FAANG Standard

Ba điều phải nắm vững

1. Tại sao Merge Sort stable còn Quick Sort thì không? Merge Sort giữ thứ tự tương đối khi merge (lấy phần tử trái trước khi bằng nhau). Quick Sort có thể swap phần tử bằng nhau qua pivot.

2. Counting inversions — FAANG-level trick Đếm số cặp $(i,j)$ với $i<j$ nhưng $arr[i]>arr[j]$. Giải bằng merge sort: khi gộp, mỗi lần lấy từ mảng phải trước mảng trái, số inversions tăng thêm (số phần tử còn lại ở mảng trái).

3. Custom comparator — không chỉ sort số JavaScript’s Array.sort() nhận comparator (a, b) => number. Sign quan trọng, không phải magnitude: < 0 (a trước b), 0 (bằng nhau), > 0 (b trước a).

Tại sao JavaScript dùng Tim Sort?

Tim Sort = Merge Sort + Insertion Sort hybrid. Tận dụng “runs” (dãy đã sorted sẵn trong data thực tế). Stable, $O(N\log N)$ worst case, $O(N)$ best case (đã sorted). Được dùng trong Python, Java, JavaScript.

---

3. Visual Thinking (Mermaid)

3.1 Merge Sort — Divide and Conquer Tree

graph TD
    A["[38, 27, 43, 3, 9, 82, 10]"] --> B["[38, 27, 43, 3]"]
    A --> C["[9, 82, 10]"]

    B --> D["[38, 27]"]
    B --> E["[43, 3]"]
    C --> F["[9, 82]"]
    C --> G["[10]"]

    D --> H["[38]"]
    D --> I["[27]"]
    E --> J["[43]"]
    E --> K["[3]"]
    F --> L["[9]"]
    F --> M["[82]"]

    H --> N["[27, 38] ←merge"]
    I --> N
    J --> O["[3, 43] ←merge"]
    K --> O
    L --> P["[9, 82] ←merge"]
    M --> P

    N --> Q["[3, 27, 38, 43] ←merge"]
    O --> Q
    P --> R["[9, 10, 82] ←merge"]
    G --> R

    Q --> S["[3, 9, 10, 27, 38, 43, 82] ✓"]
    R --> S

    style S fill:#1a4731,color:#fff

3.2 Quick Sort — Lomuto Partition Scheme

graph TD
    A["arr=[3,6,8,10,1,2,1], pivot=arr[6]=1"] --> B

    B["i=-1 (pointer for smaller elements)<br/>j scans từ 0 đến 5"] --> C

    C["j=0: arr[0]=3 > pivot=1, no swap"] --> D
    D["j=1: arr[1]=6 > pivot=1, no swap"] --> E
    E["...j=4: arr[4]=1 <= pivot → i=0, swap(arr[0],arr[4])<br/>arr=[1,6,8,10,3,2,1]"] --> F
    F["j=5: arr[5]=2 > pivot=1, no swap"] --> G
    G["Cuối: swap(arr[i+1], arr[n-1])<br/>arr=[1,1,8,10,3,2,6], pivot tại index 1"] --> H

    H["Recursion: sort [1] và [8,10,3,2,6] riêng"]

    style G fill:#2d1b69,color:#fff

3.3 Space Comparison: Merge Sort vs Quick Sort

graph LR
    subgraph MergeSpace["Merge Sort — O(N) space"]
        MS1["Level 0: 1 array size N"]
        MS2["Level 1: 2 arrays size N/2 each → vẫn O(N) tổng"]
        MS3["Auxiliary array cố định O(N) tại mỗi level"]
    end

    subgraph QuickSpace["Quick Sort — O(log N) space"]
        QS1["In-place partitioning — không cần extra array"]
        QS2["Chỉ dùng call stack: O(log N) depth trung bình"]
        QS3["Worst case stack: O(N) nếu pivot luôn là min/max"]
    end

---

4. TypeScript Template

4.1 Merge Sort — Complete Implementation

/**
 * Merge Sort — Stable, O(N log N) guaranteed
 * Time: O(N log N) all cases | Space: O(N) auxiliary
 */
function mergeSort(arr: number[]): number[] {
    // Base case: array of 0 or 1 elements is already sorted
    if (arr.length <= 1) return arr;
 
    const mid = Math.floor(arr.length / 2);
 
    // Divide
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
 
    // Conquer (merge sorted halves)
    return merge(left, right);
}

4.2 Merge Helper — Core Operation

/**
 * Gộp hai mảng đã sorted thành một mảng sorted
 * Key: khi arr[left[i]] === arr[right[j]], lấy từ LEFT trước → stable sort
 */
function merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let i = 0; // pointer cho left
    let j = 0; // pointer cho right
 
    while (i < left.length && j < right.length) {
        // Lấy left khi bằng nhau → đảm bảo stability
        if (left[i] <= right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }
 
    // Thêm phần còn lại (đã sorted) của mảng chưa duyệt hết
    while (i < left.length) result.push(left[i++]);
    while (j < right.length) result.push(right[j++]);
 
    return result;
}

4.3 Quick Sort với Random Pivot

/**
 * Quick Sort với random pivot — tránh O(N²) worst case
 * Time: O(N log N) average, O(N²) worst | Space: O(log N) stack
 *
 * Tại sao random pivot?
 * - Sorted/reverse-sorted input + first/last pivot → O(N²)
 * - Random pivot → xác suất O(N²) cực kỳ thấp với input thực tế
 */
function quickSort(arr: number[], lo: number = 0, hi: number = arr.length - 1): void {
    if (lo >= hi) return;
 
    // Randomize: swap một phần tử ngẫu nhiên về cuối làm pivot
    const randIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
    [arr[randIdx], arr[hi]] = [arr[hi], arr[randIdx]];
 
    const pivotIdx = partition(arr, lo, hi);
 
    quickSort(arr, lo, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, hi);
}

4.4 Partition — Lomuto Scheme

/**
 * Lomuto partition: pivot = arr[hi]
 * Sau khi partition: arr[pivotIdx] ở đúng vị trí final
 * - Mọi phần tử trái < arr[pivotIdx]
 * - Mọi phần tử phải > arr[pivotIdx]
 */
function partition(arr: number[], lo: number, hi: number): number {
    const pivot = arr[hi];
    let i = lo - 1; // boundary: tất cả arr[lo..i] < pivot
 
    for (let j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]]; // đưa phần tử nhỏ về phía trái
        }
    }
 
    // Đặt pivot vào đúng vị trí
    [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
    return i + 1;
}

4.5 Count Inversions Using Merge Sort

/**
 * Đếm số cặp (i, j) với i < j và arr[i] > arr[j]
 *
 * Key insight: trong bước merge, khi ta lấy arr[right[j]] trước arr[left[i]],
 * thì arr[left[i]] > arr[right[j]], nghĩa là tất cả phần tử còn lại trong
 * mảng trái (từ i đến mid) đều lớn hơn arr[right[j]] → mỗi lần như vậy
 * số inversions tăng thêm (mid - i + 1)
 *
 * Time: O(N log N) | Space: O(N)
 */
function countInversions(arr: number[]): number {
    const [, count] = mergeSortCount([...arr]);
    return count;
}
 
function mergeSortCount(arr: number[]): [number[], number] {
    if (arr.length <= 1) return [arr, 0];
 
    const mid = Math.floor(arr.length / 2);
    const [left, leftCount] = mergeSortCount(arr.slice(0, mid));
    const [right, rightCount] = mergeSortCount(arr.slice(mid));
    const [merged, splitCount] = mergeCount(left, right);
 
    return [merged, leftCount + rightCount + splitCount];
}
 
function mergeCount(left: number[], right: number[]): [number[], number] {
    const result: number[] = [];
    let inversions = 0;
    let i = 0;
    let j = 0;
 
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i]);
            i++;
        } else {
            // left[i] > right[j]: left[i..end] đều > right[j]
            // → có (left.length - i) inversions với right[j]
            inversions += left.length - i;
            result.push(right[j]);
            j++;
        }
    }
 
    while (i < left.length) result.push(left[i++]);
    while (j < right.length) result.push(right[j++]);
 
    return [result, inversions];
}
 
// Example: [2, 4, 1, 3, 5]
// Inversions: (2,1), (4,1), (4,3) → 3 inversions

4.6 Custom Sort — Multiple Keys

/**
 * Sort mảng objects theo nhiều tiêu chí
 * Ví dụ: sort meetings theo start time, nếu bằng thì theo duration
 */
interface Meeting {
    start: number;
    end: number;
    name: string;
}
 
function sortMeetings(meetings: Meeting[]): Meeting[] {
    return [...meetings].sort((a, b) => {
        // Primary key: start time (ascending)
        if (a.start !== b.start) return a.start - b.start;
 
        // Secondary key: duration (ascending)
        const durationA = a.end - a.start;
        const durationB = b.end - b.start;
        if (durationA !== durationB) return durationA - durationB;
 
        // Tertiary key: name (alphabetical)
        return a.name.localeCompare(b.name);
    });
}
 
// QUAN TRỌNG: Comparator phải return:
// - Số âm: a nên đứng trước b
// - 0: thứ tự không quan trọng (giữ nguyên nếu stable sort)
// - Số dương: b nên đứng trước a
// Chỉ sign quan trọng, không phải magnitude!

---

5. Complexity Deep-dive

Merge Sort: Master Theorem

Recurrence: $T(N)=2T\left(\frac{N}{2}\right)+O(N)$

Theo Master Theorem: $a=2$, $b=2$, $f(N)=O(N)$, $N^{{\log }_{b}a}=N^1=N$

Vì $f(N)=\Theta (N^{{\log }_{b}a})$ → Case 2: $T(N)=O(N\log N)$

Trực quan bằng cây recursion:

Level 0: 1 subproblem size N     → N work
Level 1: 2 subproblems size N/2  → N/2 + N/2 = N work
Level 2: 4 subproblems size N/4  → 4 × N/4 = N work
...
Level k: 2^k subproblems size N/2^k → N work
Total levels: log₂N
Total: N × log₂N = O(N log N) ✓

Quick Sort: Trường hợp trung bình vs xấu nhất

Average case (random pivot chia đôi tốt): $T(N)\approx 2T\left(\frac{N}{2}\right)+O(N)=O(N\log N)$

Worst case (pivot luôn là min/max, sorted input): $T(N)=T(N-1)+O(N)=O(N^2)$

Tại sao? Pivot tạo partition $[0]+[N-1]$ thay vì $[N/2]+[N/2]$ → cây recursion thành linked list.

Random Pivot Cứu Quicksort

Với random pivot, xác suất luôn chọn được pivot trong 25%-75% range là 50%. Expected depth của recursion tree: $O(\log N)$. Expected total work: $O(N\log N)$.

Counting Inversions

• Giống hệt merge sort: $O(N\log N)$
• Mỗi bước merge đếm thêm inversions trong $O(1)$ per element
• Tổng: $O(N)$ per merge level × $O(\log N)$ levels = $O(N\log N)$

---

6. Edge Cases & Pitfalls

Pitfall #1 — Quicksort Worst Case trên Sorted Input

// Input: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
// Pivot luôn = arr[hi] = phần tử lớn nhất → partition cho [0 phần tử | pivot | N-1 phần tử]
// T(N) = T(N-1) + N → O(N²)
 
// FIX: Random pivot
const randIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
[arr[randIdx], arr[hi]] = [arr[hi], arr[randIdx]];

Pitfall #2 — Merge Sort Cần O(N) Extra Space

// Merge Sort KHÔNG in-place — luôn cần array phụ
// Nếu interviewer yêu cầu O(1) space sort → phải dùng quicksort hoặc heapsort
// Trong-place merge là O(N²) hoặc rất phức tạp
 
// Khi nào chọn Merge Sort: cần stable sort, worst case guarantee, sort linked list
// Khi nào chọn Quick Sort: cần in-place, cache-friendly, average case speed

Pitfall #3 — Comparator: Sign Matters, Not Magnitude

// SAI — tưởng đúng nhưng có thể fail với số âm hoặc overflow
arr.sort((a, b) => {
    if (a > b) return 1;
    if (a < b) return -1;
    return 0;
});
 
// CŨNG ĐÚNG (ngắn hơn) — nhưng chú ý overflow với số rất lớn/nhỏ
arr.sort((a, b) => a - b); // ascending
 
// SAI khi so sánh strings:
arr.sort((a, b) => a - b); // "10" - "9" = NaN!
// ĐÚNG:
arr.sort((a, b) => a.localeCompare(b));

Pitfall #4 — Stable vs Unstable Sort

// Unstable sort có thể phá vỡ thứ tự đã có
const people = [
    { name: "Alice", age: 25 },
    { name: "Bob",   age: 25 },
    { name: "Carol", age: 30 }
];
 
// Sau khi sort theo age:
// Unstable: Alice và Bob có thể đổi thứ tự cho nhau
// Stable: Alice vẫn trước Bob (vì Alice trước Bob ban đầu)
 
// JavaScript's Array.sort() là STABLE từ ES2019 (V8, SpiderMonkey)
// → Có thể sort theo nhiều tiêu chí bằng cách sort nhiều lần (stable guarantees)

Pitfall #5 — Off-by-one trong Merge

// Tính mid cho quicksort/mergesort
const mid = Math.floor((lo + hi) / 2);
// hoặc an toàn hơn:
const mid = lo + Math.floor((hi - lo) / 2);
 
// Merge sort: right subarray bắt đầu từ mid+1, KHÔNG phải mid
mergeSort(arr, lo, mid);
mergeSort(arr, mid + 1, hi); // ← mid+1, không phải mid!
 
// Quick sort: sau khi partition, pivot tại pivotIdx đã đúng vị trí
// → không include pivot trong hai recursive calls
quickSort(arr, lo, pivotIdx - 1);
quickSort(arr, pivotIdx + 1, hi); // ← pivotIdx+1, không phải pivotIdx!

---

7. Pattern Recognition

Từ khóa nhận dạng

Merge Sort patterns:

• “Count inversions” → merge sort với inversion counting
• “Sort linked list” → merge sort (quicksort khó implement trên linked list)
• “External sort” (data không fit in memory) → merge sort
• “Stable sort required” → merge sort

Quick Sort patterns:

• “Kth largest/smallest element” → quickselect (partial quicksort) → $O(N)$ average
• “Sort in-place, O(1) space” → quicksort

Sort then Two Pointers:

• “Meeting rooms” → sort by start time
• “Merge intervals” → sort by start, merge overlapping
• “3Sum” → sort, then two pointers

Common FAANG combo:

Bài toán → Sort trước → Apply thuật toán khác (BFS/DP/Two Pointers)
Dấu hiệu: thứ tự không quan trọng với input, cần tìm pair/group thỏa điều kiện

---

8. Top LeetCode Problems

#	Tên	Độ khó	Pattern	Ghi chú
LC-912 #912	Sort an Array	Medium	Implement Merge/Quick Sort	Bài luyện implement
LC-56 #56	Merge Intervals	Medium	Sort + Greedy	Sort by start, merge overlapping
LC-315 #315	Count of Smaller Numbers After Self	Hard	Merge Sort + Inversion Count	Classic inversion counting
LC-148 #148	Sort List	Medium	Merge Sort on Linked List	Không dùng quicksort ở đây
LC-215 #215	Kth Largest Element	Medium	Quickselect	Partial sort O(N) average
LC-493 #493	Reverse Pairs	Hard	Merge Sort	Variation của counting inversions

Complete Solution: #315 Count of Smaller Numbers After Self

/**
 * LeetCode #315 — Count of Smaller Numbers After Self
 *
 * Với mỗi nums[i], đếm số phần tử nhỏ hơn nums[i] nằm BÊN PHẢI nó.
 *
 * Approach: Merge Sort + Track Original Indices
 * Key insight: Đây chính xác là bài toán counting inversions, nhưng
 * thay vì đếm tổng, ta đếm per-element.
 *
 * Khi merge: nếu ta lấy right[j] trước left[i], thì right[j] < left[i]
 * và right[j] ban đầu ở bên phải left[i] → đây là inversion
 * → tăng count[original_index_of_left[i]] lên 1
 *
 * Trick: Dùng mảng (value, originalIndex) để track sau khi sort
 *
 * Time: O(N log N) | Space: O(N)
 */
function countSmaller(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(0);
 
    // Tạo array với (value, originalIndex)
    let indexed = nums.map((val, idx) => [val, idx]);
 
    function mergeCount(arr: number[][]): number[][] {
        if (arr.length <= 1) return arr;
 
        const mid = Math.floor(arr.length / 2);
        const left = mergeCount(arr.slice(0, mid));
        const right = mergeCount(arr.slice(mid));
 
        return mergeAndCount(left, right);
    }
 
    function mergeAndCount(left: number[][], right: number[][]): number[][] {
        const merged: number[][] = [];
        let i = 0;
        let j = 0;
 
        while (i < left.length && j < right.length) {
            if (left[i][0] <= right[j][0]) {
                // Lấy từ left trước
                // Đã có j phần tử từ right được lấy trước left[i]
                // → j phần tử đó đều nhỏ hơn left[i][0] và ở bên phải
                result[left[i][1]] += j;
                merged.push(left[i]);
                i++;
            } else {
                // right[j][0] < left[i][0] → lấy right trước
                merged.push(right[j]);
                j++;
            }
        }
 
        // Phần còn lại của left: mỗi phần tử có thêm j inversions với right
        while (i < left.length) {
            result[left[i][1]] += j;
            merged.push(left[i]);
            i++;
        }
 
        while (j < right.length) {
            merged.push(right[j]);
            j++;
        }
 
        return merged;
    }
 
    mergeCount(indexed);
    return result;
}
 
/*
 * Walkthrough: nums = [5, 2, 6, 1]
 *
 * indexed = [[5,0], [2,1], [6,2], [1,3]]
 *
 * mergeCount([[5,0],[2,1],[6,2],[1,3]])
 *   left = mergeCount([[5,0],[2,1]])
 *     left = [[5,0]], right = [[2,1]]
 *     merge: right[0]=[2,1] < left[0]=[5,0] → lấy right, j=1
 *            left[0]=[5,0]: result[0] += 1 → result=[1,0,0,0]
 *     merged = [[2,1],[5,0]]
 *
 *   right = mergeCount([[6,2],[1,3]])
 *     left = [[6,2]], right = [[1,3]]
 *     merge: right[0]=[1,3] < left[0]=[6,2] → lấy right, j=1
 *            left[0]=[6,2]: result[2] += 1 → result=[1,0,1,0]
 *     merged = [[1,3],[6,2]]
 *
 *   merge [[2,1],[5,0]] với [[1,3],[6,2]]:
 *     right[0]=[1,3] < left[0]=[2,1] → lấy right, j=1
 *     left[0]=[2,1]: result[1] += 1 → result=[1,1,1,0]
 *     left[1]=[5,0]: left[1][0]=5 <= right[1][0]=6 → result[0] += 1 → result=[2,1,1,0]
 *     right[1]=[6,2]: lấy right
 *
 * Final result = [2, 1, 1, 0] ✓
 * (5 có 2 phần tử nhỏ hơn bên phải: 2,1)
 * (2 có 1 phần tử nhỏ hơn: 1)
 * (6 có 1 phần tử nhỏ hơn: 1)
 * (1 có 0 phần tử nhỏ hơn)
 */

---

9. Self-Assessment Checklist

Kiểm tra mức độ thành thạo

Level 1 — Cơ bản:

• Implement được merge sort từ đầu với merge helper
• Implement được quick sort với Lomuto partition
• Giải thích được tại sao merge sort stable còn quick sort thì không
• Biết khi nào dùng random pivot và tại sao

Level 2 — Intermediate:

• Giải được #56 (merge intervals) — sort + greedy pattern
• Implement được counting inversions với merge sort
• Viết được custom comparator cho objects với multiple keys
• Giải thích được Tim Sort là gì và tại sao JavaScript dùng nó

Level 3 — FAANG-ready:

• Giải được #315 (count smaller numbers) — merge sort + tracking indices
• Implement được Quickselect để tìm Kth largest trong $O(N)$ average
• Giải được #493 (reverse pairs) — variation của inversion counting
• Phân tích được khi nào quicksort tệ hơn merge sort và ngược lại

So sánh để ghi nhớ

• Cần stable sort? → Merge Sort
• Cần in-place, tiết kiệm memory? → Quick Sort
• Sort linked list? → Merge Sort (quicksort khó trên linked list)
• Kth element? → Quickselect ($O(N)$ average, không cần sort toàn bộ)
• External sort? → Merge Sort (dễ stream data từ disk)

---

Tags: sorting merge-sort quick-sort divide-and-conquer inversions FAANG Liên kết: 05-Binary-Search | 07-Hash-Table | Pattern-Divide-and-Conquer | Pattern-Sort-Then-Search