Merge Sort (การจัดเรียงแบบรวม)

Merge Sort เป็นอัลกอริทึมจัดเรียงแบบ Divide and Conquer (แบ่งและเอาชนะ) แบ่งข้อมูลเป็นส่วนย่อยจนเหลือ 1 องค์ประกอบ แล้วรวมกลับมาด้วยการจัดเรียง

ความซับซ้อน (Complexity)

แนวคิดการทำงาน

1. Divide: แบ่งอาเรย์ครึ่งล่ะครึ่งจนเหลือ 1 องค์ประกอบ
2. Conquer: จัดเรียงส่วนย่อย (ฐาน: 1 องค์ประกอบ = เรียงแล้ว)
3. Combine: รวม (Merge) สองส่วนที่เรียงแล้ว ให้เป็นส่วนใหญ่ที่เรียงแล้ว

ตัวอย่างข้อมูล

Input:  14 20 78 98 20 45
Output: 14 20 20 45 78 98

อัลกอริทึม (Pseudocode)

merge(array, left, mid, right)
  nLeft = mid - left + 1
  nRight = right - mid
  create leftArr[0..nLeft-1], rightArr[0..nRight-1]
  copy data to temp arrays

  i = 0, j = 0, k = left
  while i < nLeft AND j < nRight:
    if leftArr[i] <= rightArr[j]:
      array[k] = leftArr[i]; i++
    else:
      array[k] = rightArr[j]; j++
    k++

  copy remaining elements of leftArr (if any)
  copy remaining elements of rightArr (if any)

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

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

void merge(int *array, int l, int m, int r) {
    int nl = m - l + 1;
    int nr = r - m;
    int leftArr[nl], rightArr[nr];

    for (int i = 0; i < nl; i++) leftArr[i] = array[l + i];
    for (int j = 0; j < nr; j++) rightArr[j] = array[m + 1 + j];

    int i = 0, j = 0, k = l;
    while (i < nl && j < nr) {
        if (leftArr[i] <= rightArr[j]) array[k++] = leftArr[i++];
        else array[k++] = rightArr[j++];
    }
    while (i < nl) array[k++] = leftArr[i++];
    while (j < nr) array[k++] = rightArr[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);
    }
}

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

int main() {
    int n; cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << "Before: "; display(arr, n);
    mergeSort(arr, 0, n - 1);
    cout << "After: "; display(arr, n);
}

คุณสมบัติสำคัญ

• Stable: รักษาลำดับของค่าเท่ากัน
• Predictable: O(n log n) ทุกกรณี (ไม่มี Worst case แย่)
• External Sorting: ใช้จัดเรียงข้อมูลขนาดใหญ่ที่ไม่เข้า RAM (External Merge Sort)
• Parallelizable: แบ่งงานให้หลาย Thread/Process ได้ง่าย

ข้อเสีย

• ต้องการพื้นที่ O(n) เพิ่มเติม
• ช้ากว่า Quick Sort ในทางปฏิบัติ (Constant factor ใหญ่กว่า)
• ไม่ใช่ In-place (ยกเว้น In-place Merge Sort ที่ซับซ้อน)