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ụ

var prices = new List<int>
{
    12000, 3000, 7000, 5000, 450000, 25000
};
List<int> sorted = MergeSort(prices);
Console.WriteLine(string.Join(", ", sorted));

List<int> MergeSort(List<int> items)
{
    if (items.Count <= 1)
    {
        return items;
    }
    int mid = items.Count / 2;
    List<int> left = MergeSort(items.GetRange(0, mid));
    List<int> right = MergeSort(
        items.GetRange(mid, items.Count - mid));
    return Merge(left, right);
}

List<int> Merge(List<int> left, List<int> right)
{
    var result = new List<int>();
    int i = 0;
    int j = 0;
    while (i < left.Count && j < right.Count)
    {
        if (left[i] <= right[j])
        {
            result.Add(left[i]);
            i++;
        }
        else
        {
            result.Add(right[j]);
            j++;
        }
    }
    while (i < left.Count)
    {
        result.Add(left[i]);
        i++;
    }
    while (j < right.Count)
    {
        result.Add(right[j]);
        j++;
    }
    return result;
}

Điểm dừng: dãy 0 hoặc 1 phần tử đã có thứ tự, như bài Đệ quy.
GetRange(start, count) lấy một đoạn của list thành 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 khi chia và trộn, nên tốn thêm bộ nhớ cỡ n.

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

var prices = new List<int> { 12000, 3000, 7000, 5000 };
List<int> sorted = MergeSort(prices);
Console.WriteLine(string.Join(", ", sorted));

List<int> MergeSort(List<int> items)
{
    if (items.Count <= 1)
    {
        return items;
    }
    int mid = items.Count / 2;
    List<int> left = MergeSort(items.GetRange(0, mid));
    List<int> right = MergeSort(
        items.GetRange(mid, items.Count - mid));
    return Merge(left, right);
}

List<int> Merge(List<int> left, List<int> right)
{
    var result = new List<int>();
    int i = 0;
    int j = 0;
    while (i < left.Count && j < right.Count)
    {
        if (left[i] <= right[j])
        {
            result.Add(left[i]);
            i++;
        }
        else
        {
            result.Add(right[j]);
            j++;
        }
    }
    while (i < left.Count)
    {
        result.Add(left[i]);
        i++;
    }
    while (j < right.Count)
    {
        result.Add(right[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

Thêm dòng này vào MergeSort, ngay trên return Merge(left, right);:

Console.WriteLine(
    $"Trộn [{string.Join(", ", left)}]"
    + $" + [{string.Join(", ", right)}]");

Đ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.Count && j < right.Count)
{
    // lấy phần tử nhỏ hơn
}
return result;

// ĐÚNG — chép nốt bên chưa hết
while (i < left.Count)
{
    result.Add(left[i]);
    i++;
}
while (j < right.Count)
{
    result.Add(right[j]);
    j++;
}
return result;

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ụ

var prices = new List<int>
{
    12000, 3000, 7000, 5000, 450000, 25000
};
List<int> sorted = MergeSort(prices);
Console.WriteLine(string.Join(", ", sorted));

List<int> MergeSort(List<int> items)
{
    if (items.Count <= 1)
    {
        return items;
    }
    int mid = items.Count / 2;
    List<int> left = MergeSort(items.GetRange(0, mid));
    List<int> right = MergeSort(
        items.GetRange(mid, items.Count - mid));
    return Merge(left, right);
}

List<int> Merge(List<int> left, List<int> right)
{
    var result = new List<int>();
    int i = 0;
    int j = 0;
    while (i < left.Count && j < right.Count)
    {
        if (left[i] <= right[j])
        {
            result.Add(left[i]);
            i++;
        }
        else
        {
            result.Add(right[j]);
            j++;
        }
    }
    while (i < left.Count)
    {
        result.Add(left[i]);
        i++;
    }
    while (j < right.Count)
    {
        result.Add(right[j]);
        j++;
    }
    return result;
}

Điểm dừng: dãy 0 hoặc 1 phần tử đã có thứ tự, như bài Đệ quy.
GetRange(start, count) lấy một đoạn của list thành 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 khi chia và trộn, nên tốn thêm bộ nhớ cỡ n.

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

var prices = new List<int> { 12000, 3000, 7000, 5000 };
List<int> sorted = MergeSort(prices);
Console.WriteLine(string.Join(", ", sorted));

List<int> MergeSort(List<int> items)
{
    if (items.Count <= 1)
    {
        return items;
    }
    int mid = items.Count / 2;
    List<int> left = MergeSort(items.GetRange(0, mid));
    List<int> right = MergeSort(
        items.GetRange(mid, items.Count - mid));
    return Merge(left, right);
}

List<int> Merge(List<int> left, List<int> right)
{
    var result = new List<int>();
    int i = 0;
    int j = 0;
    while (i < left.Count && j < right.Count)
    {
        if (left[i] <= right[j])
        {
            result.Add(left[i]);
            i++;
        }
        else
        {
            result.Add(right[j]);
            j++;
        }
    }
    while (i < left.Count)
    {
        result.Add(left[i]);
        i++;
    }
    while (j < right.Count)
    {
        result.Add(right[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

Thêm dòng này vào MergeSort, ngay trên return Merge(left, right);:

Console.WriteLine(
    $"Trộn [{string.Join(", ", left)}]"
    + $" + [{string.Join(", ", right)}]");

Đ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.Count && j < right.Count)
{
    // lấy phần tử nhỏ hơn
}
return result;

// ĐÚNG — chép nốt bên chưa hết
while (i < left.Count)
{
    result.Add(left[i]);
    i++;
}
while (j < right.Count)
{
    result.Add(right[j]);
    j++;
}
return result;

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