Tim Sort Algorithm ใน C++

Tim Sort คืออะไร?

Timsort เป็น Hybrid Stable Sorting Algorithm ผสมระหว่าง Insertion Sort (สำหรับ Run ขนาดเล็ก) และ Merge Sort (สำหรับ Merge Runs) ใช้ใน Python, Java (Arrays.sort), Android, GNU Octave, V8 Engine

หลักการทำงาน

1. แบ่ง Array เป็น Runs ขนาดคงที่ (ปกติ 32-64 elements)
2. Sort แต่ละ Run ด้วย Insertion Sort (ดีสำหรับขนาดเล็ก/ Nearly Sorted)
3. Merge Runs ติดกันด้วย Merge Sort (ขนาด Run เพิ่มขึ้น 2x ทุกรอบ)
4. ใช้ Galloping Mode ใน Merge เพื่อเร่งเมื่อ Run หนึ่ง "ชนะ" ติดต่อกันหลายครั้ง

โค้ด C++ (Simplified)

#include <bits/stdc++.h>
using namespace std;

const int RUN = 32;

void insertionSort(int arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int temp = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

void merge(int arr[], int l, int m, int r) {
    int len1 = m - l + 1, len2 = r - m;
    vector<int> left(len1), right(len2);
    
    for (int i = 0; i < len1; i++) left[i] = arr[l + i];
    for (int i = 0; i < len2; i++) right[i] = arr[m + 1 + i];
    
    int i = 0, j = 0, k = l;
    while (i < len1 && j < len2) {
        if (left[i] <= right[j]) arr[k++] = left[i++];
        else arr[k++] = right[j++];
    }
    while (i < len1) arr[k++] = left[i++];
    while (j < len2) arr[k++] = right[j++];
}

void timSort(int arr[], int n) {
    // Sort individual runs
    for (int i = 0; i < n; i += RUN) {
        insertionSort(arr, i, min(i + RUN - 1, n - 1));
    }
    
    // Merge runs
    for (int size = RUN; size < n; size = 2 * size) {
        for (int left = 0; left < n; left += 2 * size) {
            int mid = left + size - 1;
            int right = min(left + 2 * size - 1, n - 1);
            if (mid < right) merge(arr, left, mid, right);
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {-2, 7, 15, -14, 0, 15, 0, 7, -7, -4, -13, 5, 8, -14, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original: "; printArray(arr, n);
    timSort(arr, n);
    cout << "Sorted:   "; printArray(arr, n);
    
    // Test stability: Pair (value, original_index)
    struct Item { int val, idx; };
    vector<Item> items = {{5,0}, {3,1}, {5,2}, {3,3}, {1,4}};
    // Timsort is stable → (3,1) before (3,3), (5,0) before (5,2)
    
    return 0;
}

Complexity

Key Optimizations (Real Timsort)

• Natural Runs Detection: หา Run ที่ Sorted อยู่แล้ว (Ascending/Descending) แทนที่จะบังคับขนาด 32
• Minrun Calculation: คำนวณ Run Size อัจฉริยะจาก n
• Galloping: ใน Merge, ถ้า Run หนึ่งชนะติดต่อกัน → Binary Search หาจุด Insert
• Merge Balance: รักษา Stack ของ Runs ให้ Balance (Invariants)

ผลลัพธ์

Original: -2 7 15 -14 0 15 0 7 -7 -4 -13 5 8 -14 12
Sorted:   -14 -14 -13 -7 -4 -2 0 0 5 7 7 8 12 15 15

สรุป

Timsort = Adaptive, Stable, O(n log n) Worst-case, O(n) Best-case (Sorted Data) เป็น Default Sort ใน Python/Java เพราะทำงานดีกับ Real-world Data ที่มัก Nearly Sorted