Thuật toán Tim Sort trong C++

Timsort: thuật toán sắp xếp ổn định, kết hợp Insertion Sort và Merge Sort. Dùng trong Java, Python, C++ sort().

Nguyên lý

• Chia mảng thành các RUN (kích thước 32-64)
• Sắp xếp từng RUN bằng Insertion Sort
• Merge các RUN đã sắp xếp bằng Merge Sort
• Nếu mảng nhỏ hơn RUN → chỉ dùng Insertion Sort

Độ phức tạp

• Best: Ω(n)
• Average: O(n log n)
• Worst: O(n log n)

Code C++

#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 t = arr[i], j = i - 1;
        while (j >= left && t < arr[j]) { arr[j+1] = arr[j--]; }
        arr[j+1] = t;
    }
}

void merge(int arr[], int l, int m, int r) {
    int len1 = m - l + 1, len2 = r - m;
    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 timSortAlgo(int arr[], int n) {
    for (int i = 0; i < n; i += RUN)
        insertionSort(arr, i, min(i + 31, n - 1));
    for (int s = RUN; s < n; s = 2 * s)
        for (int left = 0; left < n; left += 2 * s) {
            int mid = left + s - 1;
            int right = min(left + 2 * s - 1, n - 1);
            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);
    timSortAlgo(arr, n);
    cout << "Sorted: "; printArray(arr, n);
    return 0;
}