Timsort Implementation Using C++

Timsort is a hybrid sorting algorithm derived from merge sort and insertion sort. It is designed to perform well on many kinds of real-world data. Timsort is the default sorting algorithm in Python and Java because of its efficiency and adaptability to different data types. Here’s a simplified implementation of Timsort in C++:

#include <iostream>
#include <vector>

const int MIN_MERGE = 32;

// Merge function to merge two sorted subarrays
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<int> leftArr(n1);
    std::vector<int> rightArr(n2);

    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int i = 0; i < n2; i++) {
        rightArr[i] = arr[mid + 1 + i];
    }

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    while (i < n1) {
        arr[k++] = leftArr[i++];
    }

    while (j < n2) {
        arr[k++] = rightArr[j++];
    }
}

// Insertion sort for small subarrays
void insertionSort(std::vector<int>& arr, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

// Timsort implementation
void timSort(std::vector<int>& arr) {
    int n = arr.size();

    for (int i = 0; i < n; i += MIN_MERGE) {
        insertionSort(arr, i, std::min((i + MIN_MERGE - 1), (n - 1)));
    }

    for (int size = MIN_MERGE; size < n; size = 2 * size) {
        for (int left = 0; left < n; left += 2 * size) {
            int mid = left + size - 1;
            int right = std::min((left + 2 * size - 1), (n - 1));

            if (mid < right) {
                merge(arr, left, mid, right);
            }
        }
    }
}

int main() {
    std::vector<int> arr = {5, 1, 9, 3, 7, 6};

    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    timSort(arr);

    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

This code demonstrates a simplified Timsort implementation in C++. It defines the merge, insertionSort, and timSort functions to perform merging, insertion sort for small subarrays, and the main Timsort algorithm, respectively. The MIN_MERGE constant controls the minimum size for the subarrays that will be sorted with insertion sort.

This code is for educational purposes and may not be as optimized or efficient as a production-ready Timsort implementation. Production use cases should consider using standard library sorting functions or libraries that provide efficient sorting algorithms.