Merge sort

Sắp xếp chèn chậm hẳn khi dữ liệu lớn. Merge sort chia dãy làm đôi, sắp xếp từng nửa bằng cách gọi lại chính nó, rồi trộn hai nửa đã có thứ tự. Cách gọi lại chính nó này là đệ quy, đã học ở chương 1.

Khái niệm

🔪 Chia để trị (divide and conquer): chia bài toán thành các bài toán nhỏ cùng dạng, giải từng phần, rồi ghép kết quả.

🪡 Trộn (merge): ghép hai dãy đã có thứ tự thành một dãy có thứ tự, bằng cách mỗi lần lấy phần tử nhỏ hơn ở đầu hai dãy.

Chia đôi liên tục thì có khoảng log n tầng, mỗi tầng trộn tổng cộng n phần tử, nên merge sort luôn là O(n log n), kể cả khi dãy đầu vào xếp ngược.

Ví dụ

// Main.java
void main() {
    List<Integer> prices = List.of(
        12000, 3000, 7000, 5000, 450000, 25000);
    List<Integer> sorted = mergeSort(prices);
    System.out.println(sorted);
}

List<Integer> mergeSort(List<Integer> items) {
    if (items.size() <= 1) {
        return items;
    }
    int mid = items.size() / 2;
    List<Integer> left =
        mergeSort(items.subList(0, mid));
    List<Integer> right =
        mergeSort(items.subList(mid, items.size()));
    return merge(left, right);
}

List<Integer> merge(List<Integer> left,
        List<Integer> right) {
    List<Integer> result = new ArrayList<>();
    int i = 0;
    int j = 0;
    while (i < left.size() && j < right.size()) {
        if (left.get(i) <= right.get(j)) {
            result.add(left.get(i));
            i++;
        } else {
            result.add(right.get(j));
            j++;
        }
    }
    while (i < left.size()) {
        result.add(left.get(i));
        i++;
    }
    while (j < right.size()) {
        result.add(right.get(j));
        j++;
    }
    return result;
}

Điểm dừng: dãy 0 hoặc 1 phần tử đã có thứ tự, như bài Đệ quy.
subList(from, to) lấy đoạn từ vị trí from tới ngay trước to, không chép phần tử sang list mới.
merge so hai phần tử ở đầu hai list, lấy cái nhỏ hơn. Một bên hết thì chép nốt bên kia.
Merge sort tạo list mới mỗi lần trộn, nên tốn thêm bộ nhớ cỡ n.

▶ Mô phỏng: Chia đôi rồi trộn

void main() {
    List<Integer> prices = List.of(12000, 3000, 7000, 5000);
    System.out.println(mergeSort(prices));
}

List<Integer> mergeSort(List<Integer> items) {
    if (items.size() <= 1) {
        return items;
    }
    int mid = items.size() / 2;
    List<Integer> left =
        mergeSort(items.subList(0, mid));
    List<Integer> right =
        mergeSort(items.subList(mid, items.size()));
    return merge(left, right);
}

List<Integer> merge(List<Integer> left,
        List<Integer> right) {
    List<Integer> result = new ArrayList<>();
    int i = 0;
    int j = 0;
    while (i < left.size() && j < right.size()) {
        if (left.get(i) <= right.get(j)) {
            result.add(left.get(i));
            i++;
        } else {
            result.add(right.get(j));
            j++;
        }
    }
    while (i < left.size()) {
        result.add(left.get(i));
        i++;
    }
    while (j < right.size()) {
        result.add(right.get(j));
        j++;
    }
    return result;
}

Xem từng bước

mergeSort([12000, 3000, 7000, 5000]): mid = 4 / 2 = 2. Chia thành [12000, 3000] và [7000, 5000], sắp xếp từng nửa.
mergeSort([12000, 3000]): mid = 2 / 2 = 1. Chia thành [12000] và [3000], sắp xếp từng nửa.
mergeSort([12000]): 1 phần tử đã có thứ tự, trả về luôn (điểm dừng).
mergeSort([3000]): 1 phần tử đã có thứ tự, trả về luôn (điểm dừng).
Trộn [12000] với [3000]: hai nửa đã có thứ tự, mỗi lần lấy phần tử nhỏ hơn ở đầu hai nửa.
So lần 1: 12000 > 3000, lấy 3000 bên phải.
Bên phải đã hết: chép nốt 12000, không phải so.
mergeSort([7000, 5000]): mid = 2 / 2 = 1. Chia thành [7000] và [5000], sắp xếp từng nửa.
mergeSort([7000]): 1 phần tử đã có thứ tự, trả về luôn (điểm dừng).
mergeSort([5000]): 1 phần tử đã có thứ tự, trả về luôn (điểm dừng).
Trộn [7000] với [5000]: hai nửa đã có thứ tự, mỗi lần lấy phần tử nhỏ hơn ở đầu hai nửa.
So lần 2: 7000 > 5000, lấy 5000 bên phải.
Bên phải đã hết: chép nốt 7000, không phải so.
Trộn [3000, 12000] với [5000, 7000]: hai nửa đã có thứ tự, mỗi lần lấy phần tử nhỏ hơn ở đầu hai nửa.
So lần 3: 3000 <= 5000, lấy 3000 bên trái.
So lần 4: 12000 > 5000, lấy 5000 bên phải.
So lần 5: 12000 > 7000, lấy 7000 bên phải.
Bên phải đã hết: chép nốt 12000, không phải so.
Xong sau 5 lần so: 2 tầng chia đôi, mỗi tầng trộn tổng cộng 4 phần tử, nên là O(n log n).

Thử ngay

Trong mergeSort, ngay trên return merge(left, right);, thêm dòng System.out.println("Trộn %s + %s".formatted(left, right)); rồi chạy lại. Một list in ra dạng [3000, 7000].

Đoán trước khi chạy: với 6 giá trong ví dụ, lần trộn đầu tiên và lần trộn cuối cùng là gì?

Xem kết quả

Trộn [3000] + [7000]
Trộn [12000] + [3000, 7000]
Trộn [450000] + [25000]
Trộn [5000] + [25000, 450000]
Trộn [3000, 7000, 12000] + [5000, 25000, 450000]
[3000, 5000, 7000, 12000, 25000, 450000]

Nửa trái 12000, 3000, 7000 chia thành 12000 và 3000, 7000, rồi 3000, 7000 chia tiếp thành hai phần tử đơn. Hai phần tử này được trộn đầu tiên. Lần trộn cuối ghép hai nửa lớn đã có thứ tự.

Lỗi hay gặp

Quên chép phần còn lại sau vòng trộn chính. Vòng while đầu dừng khi một bên hết. Thiếu hai vòng sau thì mất phần tử của bên còn lại.

// SAI — thiếu phần còn lại, kết quả hụt phần tử
while (i < left.size() && j < right.size()) {
    // lấy phần tử nhỏ hơn
}
return result;

// ĐÚNG — chép nốt bên chưa hết
// Main.java
void main() {
    System.out.println(merge(
        List.of(3000, 12000), List.of(5000)));
    // [3000, 5000, 12000]
}

List<Integer> merge(List<Integer> left,
        List<Integer> right) {
    List<Integer> result = new ArrayList<>();
    int i = 0;
    int j = 0;
    while (i < left.size() && j < right.size()) {
        if (left.get(i) <= right.get(j)) {
            result.add(left.get(i));
            i++;
        } else {
            result.add(right.get(j));
            j++;
        }
    }
    while (i < left.size()) {
        result.add(left.get(i));
        i++;
    }
    while (j < right.size()) {
        result.add(right.get(j));
        j++;
    }
    return result;
}

Với [3000, 12000] và [5000], bản thiếu hai vòng sau chỉ trả [3000, 5000]: bên phải hết sau hai lần so, 12000 bị bỏ lại.

Tóm tắt

Merge sort chia đôi, sắp xếp từng nửa bằng đệ quy, rồi trộn.
Luôn O(n log n), nhưng tốn thêm bộ nhớ cỡ n.
Trộn: lấy phần tử nhỏ hơn ở đầu hai dãy, hết một bên thì chép nốt bên kia.

Khái niệm

🔪 Chia để trị (divide and conquer): chia bài toán thành các bài toán nhỏ cùng dạng, giải từng phần, rồi ghép kết quả.

🪡 Trộn (merge): ghép hai dãy đã có thứ tự thành một dãy có thứ tự, bằng cách mỗi lần lấy phần tử nhỏ hơn ở đầu hai dãy.

Chia đôi liên tục thì có khoảng log n tầng, mỗi tầng trộn tổng cộng n phần tử, nên merge sort luôn là O(n log n), kể cả khi dãy đầu vào xếp ngược.

Ví dụ

// Main.java
void main() {
    List<Integer> prices = List.of(
        12000, 3000, 7000, 5000, 450000, 25000);
    List<Integer> sorted = mergeSort(prices);
    System.out.println(sorted);
}

List<Integer> mergeSort(List<Integer> items) {
    if (items.size() <= 1) {
        return items;
    }
    int mid = items.size() / 2;
    List<Integer> left =
        mergeSort(items.subList(0, mid));
    List<Integer> right =
        mergeSort(items.subList(mid, items.size()));
    return merge(left, right);
}

List<Integer> merge(List<Integer> left,
        List<Integer> right) {
    List<Integer> result = new ArrayList<>();
    int i = 0;
    int j = 0;
    while (i < left.size() && j < right.size()) {
        if (left.get(i) <= right.get(j)) {
            result.add(left.get(i));
            i++;
        } else {
            result.add(right.get(j));
            j++;
        }
    }
    while (i < left.size()) {
        result.add(left.get(i));
        i++;
    }
    while (j < right.size()) {
        result.add(right.get(j));
        j++;
    }
    return result;
}

Điểm dừng: dãy 0 hoặc 1 phần tử đã có thứ tự, như bài Đệ quy.
subList(from, to) lấy đoạn từ vị trí from tới ngay trước to, không chép phần tử sang list mới.
merge so hai phần tử ở đầu hai list, lấy cái nhỏ hơn. Một bên hết thì chép nốt bên kia.
Merge sort tạo list mới mỗi lần trộn, nên tốn thêm bộ nhớ cỡ n.

▶ Mô phỏng: Chia đôi rồi trộn

void main() {
    List<Integer> prices = List.of(12000, 3000, 7000, 5000);
    System.out.println(mergeSort(prices));
}

List<Integer> mergeSort(List<Integer> items) {
    if (items.size() <= 1) {
        return items;
    }
    int mid = items.size() / 2;
    List<Integer> left =
        mergeSort(items.subList(0, mid));
    List<Integer> right =
        mergeSort(items.subList(mid, items.size()));
    return merge(left, right);
}

List<Integer> merge(List<Integer> left,
        List<Integer> right) {
    List<Integer> result = new ArrayList<>();
    int i = 0;
    int j = 0;
    while (i < left.size() && j < right.size()) {
        if (left.get(i) <= right.get(j)) {
            result.add(left.get(i));
            i++;
        } else {
            result.add(right.get(j));
            j++;
        }
    }
    while (i < left.size()) {
        result.add(left.get(i));
        i++;
    }
    while (j < right.size()) {
        result.add(right.get(j));
        j++;
    }
    return result;
}

Xem từng bước

mergeSort([12000, 3000, 7000, 5000]): mid = 4 / 2 = 2. Chia thành [12000, 3000] và [7000, 5000], sắp xếp từng nửa.
mergeSort([12000, 3000]): mid = 2 / 2 = 1. Chia thành [12000] và [3000], sắp xếp từng nửa.
mergeSort([12000]): 1 phần tử đã có thứ tự, trả về luôn (điểm dừng).
mergeSort([3000]): 1 phần tử đã có thứ tự, trả về luôn (điểm dừng).
Trộn [12000] với [3000]: hai nửa đã có thứ tự, mỗi lần lấy phần tử nhỏ hơn ở đầu hai nửa.
So lần 1: 12000 > 3000, lấy 3000 bên phải.
Bên phải đã hết: chép nốt 12000, không phải so.
mergeSort([7000, 5000]): mid = 2 / 2 = 1. Chia thành [7000] và [5000], sắp xếp từng nửa.
mergeSort([7000]): 1 phần tử đã có thứ tự, trả về luôn (điểm dừng).
mergeSort([5000]): 1 phần tử đã có thứ tự, trả về luôn (điểm dừng).
Trộn [7000] với [5000]: hai nửa đã có thứ tự, mỗi lần lấy phần tử nhỏ hơn ở đầu hai nửa.
So lần 2: 7000 > 5000, lấy 5000 bên phải.
Bên phải đã hết: chép nốt 7000, không phải so.
Trộn [3000, 12000] với [5000, 7000]: hai nửa đã có thứ tự, mỗi lần lấy phần tử nhỏ hơn ở đầu hai nửa.
So lần 3: 3000 <= 5000, lấy 3000 bên trái.
So lần 4: 12000 > 5000, lấy 5000 bên phải.
So lần 5: 12000 > 7000, lấy 7000 bên phải.
Bên phải đã hết: chép nốt 12000, không phải so.
Xong sau 5 lần so: 2 tầng chia đôi, mỗi tầng trộn tổng cộng 4 phần tử, nên là O(n log n).

Thử ngay

Trong mergeSort, ngay trên return merge(left, right);, thêm dòng System.out.println("Trộn %s + %s".formatted(left, right)); rồi chạy lại. Một list in ra dạng [3000, 7000].

Đoán trước khi chạy: với 6 giá trong ví dụ, lần trộn đầu tiên và lần trộn cuối cùng là gì?

Xem kết quả

Trộn [3000] + [7000]
Trộn [12000] + [3000, 7000]
Trộn [450000] + [25000]
Trộn [5000] + [25000, 450000]
Trộn [3000, 7000, 12000] + [5000, 25000, 450000]
[3000, 5000, 7000, 12000, 25000, 450000]

Lỗi hay gặp

Quên chép phần còn lại sau vòng trộn chính. Vòng while đầu dừng khi một bên hết. Thiếu hai vòng sau thì mất phần tử của bên còn lại.

// SAI — thiếu phần còn lại, kết quả hụt phần tử
while (i < left.size() && j < right.size()) {
    // lấy phần tử nhỏ hơn
}
return result;

// ĐÚNG — chép nốt bên chưa hết
// Main.java
void main() {
    System.out.println(merge(
        List.of(3000, 12000), List.of(5000)));
    // [3000, 5000, 12000]
}

List<Integer> merge(List<Integer> left,
        List<Integer> right) {
    List<Integer> result = new ArrayList<>();
    int i = 0;
    int j = 0;
    while (i < left.size() && j < right.size()) {
        if (left.get(i) <= right.get(j)) {
            result.add(left.get(i));
            i++;
        } else {
            result.add(right.get(j));
            j++;
        }
    }
    while (i < left.size()) {
        result.add(left.get(i));
        i++;
    }
    while (j < right.size()) {
        result.add(right.get(j));
        j++;
    }
    return result;
}

Với [3000, 12000] và [5000], bản thiếu hai vòng sau chỉ trả [3000, 5000]: bên phải hết sau hai lần so, 12000 bị bỏ lại.

Tóm tắt

Merge sort chia đôi, sắp xếp từng nửa bằng đệ quy, rồi trộn.
Luôn O(n log n), nhưng tốn thêm bộ nhớ cỡ n.
Trộn: lấy phần tử nhỏ hơn ở đầu hai dãy, hết một bên thì chép nốt bên kia.

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Bình luận

Merge sort

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Bình luận