Merge Sort — Sắp xếp trộn

Merge Sort là thuật toán O(n log n) đầu tiên mà hầu hết kỹ sư tiếp cận trong hành trình học thuật toán. Nhưng giá trị của nó vượt xa một bài tập trên lớp — đây là cánh cửa dẫn vào tư duy Divide & Conquer, nền tảng cho hàng loạt thuật toán quan trọng khác.

Trong thực tế production, Merge Sort là thuật toán được chọn cho external sorting — khi database cần sắp xếp dữ liệu lớn hơn RAM. PostgreSQL dùng nó cho ORDER BY trên tập dữ liệu lớn. Python's Timsort — engine đằng sau list.sort() — là hybrid giữa Merge Sort và Insertion Sort. Java's Arrays.sort() cho object arrays cũng dựa trên biến thể của Merge Sort.

Điểm khác biệt then chốt: Merge Sort không bao giờ suy giảm hiệu năng. Trong khi Quick Sort có thể rơi vào O(n²) với input xấu, Merge Sort luôn giữ O(n log n) — best, average, và worst case. Đó là lý do nó được tin dùng khi tính ổn định là yêu cầu bắt buộc.

---

Bức tranh tư duy

Hãy hình dung bạn là trưởng phòng nhân sự, cần sắp xếp 500 bộ hồ sơ theo tên nhân viên.

Bạn không thể ôm cả chồng hồ sơ mà sắp xếp một lúc. Thay vào đó, bạn áp dụng chiến thuật:

1. Chia (Divide): Tách chồng hồ sơ làm đôi, rồi tiếp tục tách cho đến khi mỗi nhóm chỉ còn 1 tờ — một tờ đơn lẻ mặc định đã "sắp xếp".
2. Trộn (Merge): Bắt đầu ghép lại — hai nhân viên đặt cạnh nhau, so sánh tên, xếp đúng thứ tự. Rồi ghép hai cặp thành nhóm 4, nhóm 4 thành nhóm 8… cho đến khi toàn bộ 500 hồ sơ xếp đúng thứ tự.

Đây chính xác là cách một đội ngũ chia việc rồi tổng hợp kết quả — mỗi người xử lý phần nhỏ, rồi ghép lại thành tổng thể.

💡 HPN's Insight

Merge Sort minh họa hoàn hảo nguyên lý "Chia để trị" (Divide and Conquer): một bài toán lớn phức tạp được phân tách thành nhiều bài toán nhỏ đơn giản, giải quyết độc lập, rồi tổng hợp. Tư duy này xuất hiện ở khắp nơi — từ MapReduce trong Big Data đến Fork/Join trong lập trình song song.

---

Cốt lõi kỹ thuật

Mô hình Divide and Conquer

Merge Sort tuân theo ba bước kinh điển của Divide and Conquer:

Bước	Hành động	Độ phức tạp
Divide	Chia mảng tại điểm giữa mid = (left + right) / 2	O(1)
Conquer	Đệ quy sắp xếp hai nửa [left..mid] và [mid+1..right]	2T(n/2)
Combine	Trộn hai mảng con đã sắp xếp thành một mảng	O(n)

Base case: mảng có 0 hoặc 1 phần tử — đã sắp xếp sẵn.

Thao tác Merge — trái tim của thuật toán

Thao tác merge là bước quyết định. Hai mảng con đã sắp xếp được trộn lại bằng kỹ thuật two-pointer:

Left:  [3, 27, 38, 43]    Right: [9, 10, 82]
        ↑                          ↑
        i                          j

Bước 1: 3 < 9  → lấy 3   → result: [3]
Bước 2: 27 > 9 → lấy 9   → result: [3, 9]
Bước 3: 27 > 10→ lấy 10  → result: [3, 9, 10]
Bước 4: 27 < 82→ lấy 27  → result: [3, 9, 10, 27]
Bước 5: 38 < 82→ lấy 38  → result: [3, 9, 10, 27, 38]
Bước 6: 43 < 82→ lấy 43  → result: [3, 9, 10, 27, 38, 43]
Bước 7: copy 82           → result: [3, 9, 10, 27, 38, 43, 82]

Mỗi phần tử được so sánh và đặt đúng vị trí đúng một lần → thao tác merge là O(n).

Top-Down Merge Sort (Đệ quy)

Đây là cài đặt chuẩn, trực quan nhất — đệ quy chia mảng từ trên xuống.

C++

#include <vector>
using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<int> leftArr(n1), rightArr(n2);

    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        // <= giữ tính stable: phần tử bằng nhau giữ nguyên thứ tự gốc
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    while (i < n1) arr[k++] = leftArr[i++];
    while (j < n2) arr[k++] = rightArr[j++];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;  // tránh overflow so với (left+right)/2
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

Python

def merge_sort(arr: list[int]) -> list[int]:
    """Merge Sort — top-down recursive, trả về mảng mới."""
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return _merge(left, right)


def _merge(left: list[int], right: list[int]) -> list[int]:
    """Trộn hai mảng đã sắp xếp thành một mảng."""
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        # <= giữ tính stable
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

Java

public class MergeSort {

    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;

        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        System.arraycopy(arr, left, leftArr, 0, n1);
        System.arraycopy(arr, mid + 1, rightArr, 0, n2);

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }
}

Go

package sorting

func MergeSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	mid := len(arr) / 2
	left := MergeSort(arr[:mid])
	right := MergeSort(arr[mid:])

	return merge(left, right)
}

func merge(left, right []int) []int {
	result := make([]int, 0, len(left)+len(right))
	i, j := 0, 0

	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}

	result = append(result, left[i:]...)
	result = append(result, right[j:]...)
	return result
}

Bottom-Up Merge Sort (Lặp)

Thay vì đệ quy từ trên xuống, bottom-up bắt đầu từ các cặp phần tử nhỏ nhất rồi nhân đôi kích thước mỗi vòng lặp. Không cần stack đệ quy — phù hợp cho hệ thống có giới hạn stack hoặc mảng rất lớn.

Mảng gốc:  [38, 27, 43, 3, 9, 82, 10]

width=1:   [27,38] [3,43] [9,82] [10]      ← merge từng cặp 1 phần tử
width=2:   [3,27,38,43] [9,10,82]           ← merge từng cặp 2 phần tử
width=4:   [3,9,10,27,38,43,82]             ← merge từng cặp 4 phần tử

C++

void mergeSortBottomUp(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return;

    vector<int> temp(n);

    for (int width = 1; width < n; width *= 2) {
        for (int left = 0; left < n; left += 2 * width) {
            int mid = min(left + width - 1, n - 1);
            int right = min(left + 2 * width - 1, n - 1);

            // Merge [left..mid] và [mid+1..right]
            int i = left, j = mid + 1, k = left;
            while (i <= mid && j <= right) {
                if (arr[i] <= arr[j]) temp[k++] = arr[i++];
                else                  temp[k++] = arr[j++];
            }
            while (i <= mid)   temp[k++] = arr[i++];
            while (j <= right) temp[k++] = arr[j++];

            for (int idx = left; idx <= right; idx++)
                arr[idx] = temp[idx];
        }
    }
}

Python

def merge_sort_bottom_up(arr: list[int]) -> list[int]:
    """Bottom-up merge sort — không đệ quy."""
    n = len(arr)
    if n <= 1:
        return arr

    result = arr[:]
    width = 1

    while width < n:
        for left in range(0, n, 2 * width):
            mid = min(left + width, n)
            right = min(left + 2 * width, n)

            # Merge result[left:mid] và result[mid:right]
            merged = []
            i, j = left, mid
            while i < mid and j < right:
                if result[i] <= result[j]:
                    merged.append(result[i])
                    i += 1
                else:
                    merged.append(result[j])
                    j += 1
            merged.extend(result[i:mid])
            merged.extend(result[j:right])

            result[left:right] = merged

        width *= 2

    return result

🎓 HPN's Comparison: Top-Down vs Bottom-Up

Top-Down trực quan hơn, dễ hiểu khi học. Bottom-Up loại bỏ overhead của đệ quy (stack frames), thực tế nhanh hơn ~5-10% cho mảng lớn. Trong production, Java's TimSort dùng bottom-up merge. Khi cài đặt cho linked list, bottom-up là lựa chọn tự nhiên vì không cần random access.

---

Thực chiến

External Merge Sort — khi dữ liệu lớn hơn RAM

Đây là ứng dụng production quan trọng nhất của Merge Sort. Khi database cần ORDER BY trên bảng 100GB mà RAM chỉ có 16GB, external merge sort là giải pháp duy nhất.

Quy trình:

1. Chia file lớn thành các chunk vừa RAM (ví dụ: 16GB file → 4 chunk × 4GB)
2. Sắp xếp từng chunk trong RAM (dùng Quick Sort hoặc Timsort)
3. Ghi chunk đã sắp xếp ra disk thành các file tạm (sorted runs)
4. K-way merge các sorted runs bằng min-heap, ghi kết quả cuối cùng

import heapq
from typing import Iterator


def external_merge_sort(
    sorted_runs: list[Iterator[int]],
    output_path: str,
    buffer_size: int = 8192
) -> None:
    """
    K-way merge cho external sorting.
    Mỗi sorted_run là iterator đọc từ file đã sắp xếp.
    """
    # Min-heap: (giá_trị, chỉ_số_run) để biết lấy phần tử tiếp từ run nào
    heap: list[tuple[int, int]] = []

    for run_idx, run in enumerate(sorted_runs):
        first_value = next(run, None)
        if first_value is not None:
            heapq.heappush(heap, (first_value, run_idx))

    with open(output_path, 'w') as out:
        buffer: list[str] = []

        while heap:
            smallest, run_idx = heapq.heappop(heap)
            buffer.append(str(smallest))

            if len(buffer) >= buffer_size:
                out.write('\n'.join(buffer) + '\n')
                buffer.clear()

            next_value = next(sorted_runs[run_idx], None)
            if next_value is not None:
                heapq.heappush(heap, (next_value, run_idx))

        if buffer:
            out.write('\n'.join(buffer) + '\n')

⚡ ENGINEERING DEEP DIVE: PostgreSQL và External Sort

PostgreSQL's tuplesort.c implement chính xác mô hình này. Khi work_mem không đủ cho toàn bộ dữ liệu, Postgres tạo sorted runs trên disk rồi merge bằng polyphase merge — một biến thể tối ưu hóa số lần đọc/ghi disk. Hiểu Merge Sort là hiểu core của database sorting.

Merge Sort cho Linked List — O(1) extra space

Merge Sort trên linked list là trường hợp lý tưởng: không cần mảng phụ O(n) vì chỉ cần chỉnh lại con trỏ. Đây là lý do Merge Sort thường được chọn thay Quick Sort khi sắp xếp linked list.

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Tìm điểm giữa bằng slow/fast pointer
ListNode* getMiddle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

ListNode* mergeSortList(ListNode* head) {
    if (!head || !head->next) return head;

    ListNode* mid = getMiddle(head);
    ListNode* rightHalf = mid->next;
    mid->next = nullptr;  // cắt đôi list

    ListNode* left = mergeSortList(head);
    ListNode* right = mergeSortList(rightHalf);
    return mergeTwoLists(left, right);
}

🌍 HPN's Real-world Application

LeetCode #148 (Sort List) yêu cầu sắp xếp linked list trong O(n log n) time và O(1) space. Merge Sort cho linked list là lời giải chuẩn. Đây cũng là câu hỏi phỏng vấn phổ biến tại Google và Meta — vì nó kiểm tra đồng thời hiểu biết về sorting, linked list manipulation, và recursion.

---

Sai lầm điển hình

❌ Sai lầm 1: Bỏ qua chi phí O(n) bộ nhớ phụ

🛑 HPN's Warning

Nhiều kỹ sư chỉ nhớ Merge Sort là O(n log n) mà quên rằng nó cần O(n) extra space cho mảng tạm. Trên hệ thống có giới hạn bộ nhớ nghiêm ngặt (embedded systems, mobile), đây là deal-breaker.

# ❌ SAI: Tạo mảng tạm mới mỗi lần gọi merge — phân mảnh bộ nhớ
def merge_bad(arr, left, mid, right):
    temp = []  # Cấp phát mới mỗi lần → garbage collection pressure
    # ...

# ✅ ĐÚNG: Cấp phát một mảng tạm duy nhất, tái sử dụng
def merge_sort_optimized(arr):
    temp = [0] * len(arr)  # Cấp phát một lần
    _sort(arr, temp, 0, len(arr) - 1)

def _sort(arr, temp, left, right):
    if left >= right:
        return
    mid = (left + right) // 2
    _sort(arr, temp, left, mid)
    _sort(arr, temp, mid + 1, right)
    _merge_with_buffer(arr, temp, left, mid, right)

❌ Sai lầm 2: Không xem xét Bottom-Up khi cần phiên bản lặp

Khi mảng rất lớn hoặc stack size bị giới hạn, top-down recursive có thể gây stack overflow với depth = O(log n). Bottom-up iterative giải quyết hoàn toàn vấn đề này mà không cần tối ưu tail-recursion.

❌ Sai lầm 3: Bug off-by-one trong bước merge

// ❌ SAI: Dùng < thay vì <= mất tính stable
if (leftArr[i] < rightArr[j])  // phần tử bằng nhau từ right đi trước → UNSTABLE

// ✅ ĐÚNG: Dùng <= để phần tử bằng nhau từ left (xuất hiện trước) đi trước
if (leftArr[i] <= rightArr[j])  // giữ thứ tự gốc → STABLE

// ❌ SAI: Tính mid sai gây overflow với số lớn
int mid = (left + right) / 2;  // overflow khi left + right > INT_MAX

// ✅ ĐÚNG: Tránh overflow
int mid = left + (right - left) / 2;

❌ Sai lầm 4: Dùng Merge Sort khi Quick Sort phù hợp hơn

⚠️ Cạm bẫy phổ biến

Merge Sort không phải lúc nào cũng tốt hơn Quick Sort. Cho sắp xếp in-memory trên mảng (random access), Quick Sort thường nhanh hơn 2-3x nhờ cache locality tốt hơn — nó truy cập bộ nhớ tuần tự, trong khi Merge Sort nhảy qua lại giữa mảng gốc và mảng tạm.

Quy tắc chọn:

• In-memory array, không cần stable → Quick Sort
• Cần stable sort hoặc worst-case guarantee → Merge Sort
• Linked list → Merge Sort (Quick Sort cần random access)
• External sorting (disk-based) → Merge Sort

---

Under the Hood

Phân tích độ phức tạp

Trường hợp	Time	Space	Ghi chú
Best	O(n log n)	O(n)	Mảng đã sắp xếp — vẫn chia và merge
Average	O(n log n)	O(n)	Mọi phân bố dữ liệu
Worst	O(n log n)	O(n)	Mảng ngược — vẫn O(n log n)
Linked list	O(n log n)	O(log n)	Chỉ tốn stack cho recursion

Recurrence Relation và Master Theorem

Merge Sort tuân theo recurrence:

$$T(n)=2T(n/2)+O(n)$$

Áp dụng Master Theorem với a=2, b=2, f(n)=O(n):

• $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n^1=n$
• $f(n)=O(n)=\mathrm{\Theta }(n^{{\log }_{b}a})$
• → Case 2: $T(n)=\mathrm{\Theta }(n\log n)$

Trực quan: có log₂(n) tầng đệ quy, mỗi tầng thực hiện tổng cộng O(n) công việc merge.

Tầng 0:  1 bài toán × n phần tử    = n công việc
Tầng 1:  2 bài toán × n/2 phần tử  = n công việc
Tầng 2:  4 bài toán × n/4 phần tử  = n công việc
...
Tầng k:  2ᵏ bài toán × n/2ᵏ phần tử = n công việc

Tổng: n × log₂(n) = O(n log n)

Tính Stable — chứng minh

Merge Sort là stable sort: hai phần tử có giá trị bằng nhau giữ nguyên thứ tự tương đối ban đầu.

Chứng minh: Trong bước merge, khi left[i] == right[j], ta chọn left[i] trước (toán tử <=). Vì left luôn chứa các phần tử xuất hiện trước trong mảng gốc, thứ tự tương đối được bảo toàn qua mọi tầng đệ quy.

Đây là lý do Java dùng Merge Sort (TimSort) cho Arrays.sort(Object[]) — khi sort object theo một field, các object có cùng giá trị field đó phải giữ nguyên thứ tự gốc.

Cache Performance — điểm yếu cần biết

⚡ ENGINEERING DEEP DIVE: Cache-unfriendly

Merge Sort truy cập bộ nhớ không tuần tự khi merge: đọc xen kẽ giữa mảng left, mảng right, và ghi vào mảng kết quả. Điều này gây cache miss nhiều hơn Quick Sort (truy cập in-place, tuần tự).

Trên CPU hiện đại với L1/L2 cache, sự khác biệt có thể lên đến 2-3x cho dữ liệu vừa trong cache. Đây là lý do chính Quick Sort thường nhanh hơn Merge Sort trên thực tế, dù cả hai đều O(n log n).

Tối ưu: Khi mảng con nhỏ hơn ngưỡng (thường 16-32 phần tử), chuyển sang Insertion Sort — đây chính là cách TimSort hoạt động.

---

Checklist ghi nhớ

✅ Checklist triển khai

Nguyên lý cốt lõi

• [ ] Merge Sort chia mảng làm đôi đệ quy, rồi merge hai nửa đã sắp xếp
• [ ] Base case: mảng 0 hoặc 1 phần tử → đã sắp xếp
• [ ] Toán tử <= trong merge giữ tính stable

Độ phức tạp

• [ ] Time: O(n log n) cho MỌI trường hợp — không có worst case degradation
• [ ] Space: O(n) cho mảng, O(log n) cho linked list
• [ ] Recurrence: T(n) = 2T(n/2) + O(n) → Master Theorem Case 2

Biến thể & ứng dụng

• [ ] Top-down (đệ quy): trực quan, dễ cài đặt
• [ ] Bottom-up (lặp): không cần stack, tốt cho mảng lớn
• [ ] External merge sort: K-way merge cho dữ liệu lớn hơn RAM
• [ ] Linked list: O(1) extra space, chỉ cần chỉnh con trỏ

Khi nào dùng / không dùng

• [ ] DÙNG khi cần stable sort hoặc worst-case O(n log n) guarantee
• [ ] DÙNG cho linked list hoặc external sorting
• [ ] KHÔNG DÙNG cho in-memory array khi Quick Sort đủ tốt (cache locality kém hơn)

---

Bài tập luyện tập

Bài 1: Merge Two Sorted Arrays — Foundation

Đề bài: Cho hai mảng đã sắp xếp nums1 (kích thước m+n, m phần tử đầu có giá trị, n phần tử cuối là 0) và nums2 (kích thước n). Merge nums2 vào nums1 in-place sao cho kết quả vẫn sắp xếp.

Ví dụ:

Input:  nums1 = [1, 2, 3, 0, 0, 0], m = 3
        nums2 = [2, 5, 6],           n = 3
Output: nums1 = [1, 2, 2, 3, 5, 6]

💡 Gợi ý

• Merge từ cuối mảng về đầu để tránh ghi đè phần tử chưa xử lý
• Dùng ba con trỏ: p1 ở cuối phần có giá trị của nums1, p2 ở cuối nums2, p ở cuối nums1

✅ Lời giải

def merge_in_place(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    p1, p2, p = m - 1, n - 1, m + n - 1

    while p1 >= 0 and p2 >= 0:
        if nums1[p1] >= nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

    # Copy phần còn lại của nums2 (nếu có)
    nums1[:p2 + 1] = nums2[:p2 + 1]

Phân tích: Time O(m+n), Space O(1). Đây là LeetCode #88 — câu hỏi phỏng vấn kinh điển.

Bài 2: Count Inversions — Intermediate

Đề bài: Đếm số cặp nghịch thế (inversion) trong mảng. Một cặp (i, j) là nghịch thế nếu i < j nhưng arr[i] > arr[j]. Yêu cầu O(n log n).

Ví dụ:

Input:  [2, 4, 1, 3, 5]
Output: 3
Giải thích: (2,1), (4,1), (4,3) là 3 cặp nghịch thế

💡 Gợi ý

• Biến đổi Merge Sort: trong bước merge, mỗi khi phần tử từ mảng right được chọn trước phần tử từ mảng left, đếm thêm số phần tử còn lại trong left
• Số inversions = inversions trong left + inversions trong right + split inversions (đếm trong merge)

✅ Lời giải

def count_inversions(arr: list[int]) -> int:
    if len(arr) <= 1:
        return 0

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    inversions = count_inversions(left) + count_inversions(right)

    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            # Mọi phần tử left[i..] đều > right[j] → đó là inversions
            inversions += len(left) - i
            arr[k] = right[j]
            j += 1
        k += 1

    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1
    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1

    return inversions

Phân tích: Time O(n log n), Space O(n). Ứng dụng: đo "khoảng cách" giữa hai ranking (collaborative filtering, recommendation systems).

🧠 Quiz

Câu hỏi kiểm tra: Merge Sort có đặc điểm nào sau đây mà Quick Sort KHÔNG có?

• [ ] A. Độ phức tạp trung bình O(n log n)
• [x] B. Luôn O(n log n) ở worst case và là stable sort
• [ ] C. Sắp xếp in-place không cần bộ nhớ phụ
• [ ] D. Cache-friendly hơn trên mảng lớn

Giải thích: Quick Sort average O(n log n) nhưng worst case O(n²) và KHÔNG stable. Merge Sort luôn O(n log n) và stable. Tuy nhiên Merge Sort cần O(n) extra space (C sai) và cache-unfriendly hơn Quick Sort (D sai).

---

Liên kết học tiếp

📚 Bài liên quan

Bài liên quan trong Penalgo

• ← Insertion Sort — Thuật toán cơ bản, base case cho Merge Sort khi mảng nhỏ
• → Quick Sort — Đối thủ trực tiếp: nhanh hơn in-memory nhưng không stable
• Độ phức tạp thuật toán — Master Theorem và phân tích recurrence
• Divide and Conquer — Paradigm chung: Merge Sort, Quick Sort, Binary Search
• Linked List — Merge Sort trên linked list là ứng dụng kinh điển