Thuật toán Merge Sort (Sắp xếp trộn)

Kỹ thuật Merge Sort dựa trên chiến lược chia để trị (divide and conquer). Chia tập dữ liệu thành các phần nhỏ hơn và trộn chúng thành phần lớn hơn theo thứ tự đã sắp xếp. Rất hiệu quả cho trường hợp xấu nhất vì độ phức tạp thời gian thấp.

Độ phức tạp Merge Sort

• Time Complexity: O(n log n) cho mọi trường hợp
• Space Complexity: O(n)

Input và Output

Input: Danh sách chưa sắp xếp: 14 20 78 98 20 45
Output: Mảng trước sắp xếp: 14 20 78 98 20 45
Mảng sau sắp xếp: 14 20 20 45 78 98

Thuật toán

merge(array, left, middle, right)

Input: Mảng dữ liệu, chỉ số left, middle, right

Output: Mảng đã trộn

Begin
  nLeft := middle - left + 1
  nRight := right - middle
  định nghĩa mảng leftArr, rightArr kích thước nLeft, nRight
  for i := 0 to nLeft-1 do
    leftArr[i] := array[left + i]
  done
  for j := 0 to nRight-1 do
    rightArr[j] := array[middle + j + 1]
  done
  i := 0, j := 0, k := left
  while i < nLeft AND j < nRight do
    if leftArr[i] <= rightArr[j] then
      array[k] = leftArr[i]
      i := i + 1
    else
      array[k] = rightArr[j]
      j := j + 1
    k := k + 1
  done
  while i < nLeft do
    array[k] := leftArr[i]
    i := i + 1
    k := k + 1
  done
  while j < nRight do
    array[k] := rightArr[j]
    j := j + 1
    k := k + 1
  done
End

mergeSort(array, left, right)

Begin
  if left < right then
    mid := left + (right - left) / 2
    mergeSort(array, left, mid)
    mergeSort(array, mid + 1, right)
    merge(array, left, mid, right)
  End

Ví dụ (C++)

#include <iostream>
using namespace std;

void display(int *array, int size) {
    for(int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

void merge(int *array, int l, int m, int r) {
    int nl = m - l + 1, nr = r - m;
    int larr[nl], rarr[nr];
    for(int i = 0; i < nl; i++) larr[i] = array[l + i];
    for(int j = 0; j < nr; j++) rarr[j] = array[m + 1 + j];
    int i = 0, j = 0, k = l;
    while(i < nl && j < nr) {
        if(larr[i] <= rarr[j]) array[k++] = larr[i++];
        else array[k++] = rarr[j++];
    }
    while(i < nl) array[k++] = larr[i++];
    while(j < nr) array[k++] = rarr[j++];
}

void mergeSort(int *array, int l, int r) {
    if(l < r) {
        int m = l + (r - l) / 2;
        mergeSort(array, l, m);
        mergeSort(array, m + 1, r);
        merge(array, l, m, r);
    }
}

int main() {
    int n; cout << "Nhập số phần tử: "; cin >> n;
    int arr[n];
    cout << "Nhập phần tử:" << endl;
    for(int i = 0; i < n; i++) cin >> arr[i];
    cout << "Trước sắp xếp: "; display(arr, n);
    mergeSort(arr, 0, n - 1);
    cout << "Sau sắp xếp: "; display(arr, n);
}

Kết quả

Nhập số phần tử: 6
Nhập phần tử: 14 20 78 98 20 45
Trước sắp xếp: 14 20 78 98 20 45
Sau sắp xếp: 14 20 20 45 78 98

Đặc điểm: Merge Sort ổn định (stable), đảm bảo O(n log n) mọi trường hợp, nhưng cần O(n) bộ nhớ phụ. Phù hợp cho linked list và sắp xếp file ngoài (external sorting).