C++-এ টিম সর্ট (Tim Sort) অ্যালগরিদম ইমপ্লিমেন্টেশন

টিম সর্ট হাইব্রিড সর্টিং অ্যালগরিদম: ইন্সার্শন সর্ট + মার্জ সর্ট। পাইথন, জাভা, সি++-র std::sort-এ ব্যবহৃত হয়। ছোট চাঙ্ক (RUN=৩২) ইন্সার্শন সর্ট দিয়ে সর্ট করে, তারপর মার্জ করে।

কমপ্লেক্সিটি

• বেস্ট: O(n) (ইরি সর্টেড)
• অভারেজ/ওৰ্স্ট: O(n log n)
• স্ট্যাবল সর্ট

অ্যালগরিদম

1. RUN সাইজ (৩২) দিয়ে অ্যারেকে চাঙ্কে ভাগ করুন।
2. প্রতিটি চাঙ্ক ইন্সার্শন সর্ট দিয়ে সর্ট করুন।
3. মার্জ সর্টের মতো চাঙ্কগুলো মার্জ করুন (সাইজ ৩২, ৬৪, ১২৮... দ্বিগুণ করে)।

উদাহরণ কোড

#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], j = i - 1;
        while (j >= left && temp < arr[j]) {
            arr[j+1] = arr[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)
        arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    while (i < len1) arr[k++] = left[i++];
    while (j < len2) arr[k++] = right[j++];
}

void timSort(int arr[], int n) {
    for (int i = 0; i < n; i += RUN)
        insertionSort(arr, i, min(i + RUN - 1, n - 1));
    
    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);
        }
    }
}

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]);
    timSort(arr, n);
    for (int x : arr) cout << x << " ";
    return 0;
}

আউটপুট

-14 -14 -13 -7 -4 -2 0 0 5 7 7 8 12 15 15