Tim Sort Algorithm

What is Timsort?

Timsort is a modern hybrid sorting algorithm derived from Merge Sort and Insertion Sort. It was designed to perform extremely well on real-world data, especially data that is partially sorted.

Timsort is the default sorting algorithm in:

• Python (since version 2.3)
• Java’s Collections.sort() and Arrays.sort(Object[])
• Android’s sort utilities

Although C++’s Standard Library does not use Timsort by default, you can implement it manually, making it a great educational project for understanding advanced sorting techniques.

Key Concepts

Timsort works by:

1. Dividing the array into small segments called runs.
2. Sorting each run using Insertion Sort (efficient for small datasets).
3. Merging the sorted runs using Merge Sort logic with optimizations.

Timsort is adaptive, meaning it performs better if the data is already partially sorted. It also preserves the order of equal elements (i.e., it is stable).

Time and Space Complexity

• Space Complexity: O(n)
• Stable: ✅ Yes

When to Use Timsort

• When data is partially sorted
• When stability is required
• For real-world datasets with unpredictable patterns

Timsort – C++ Code Example (Simplified Version)

#include <iostream>
#include <algorithm>
using namespace std;

const int RUN = 32;

// Insertion Sort used by Timsort
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;
    }
}

// Merge function used by Timsort
void merge(int arr[], int left, int mid, int right) {
    int len1 = mid - left + 1;
    int len2 = right - mid;
    int* leftArr = new int[len1];
    int* rightArr = new int[len2];

    for (int i = 0; i < len1; i++) leftArr[i] = arr[left + i];
    for (int i = 0; i < len2; i++) rightArr[i] = arr[mid + 1 + i];

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

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

    while (i < len1) arr[k++] = leftArr[i++];
    while (j < len2) arr[k++] = rightArr[j++];

    delete[] leftArr;
    delete[] rightArr;
}

// Timsort algorithm
void timSort(int arr[], int n) {
    // Step 1: Sort individual runs using insertion sort
    for (int i = 0; i < n; i += RUN) {
        insertionSort(arr, i, min(i + RUN - 1, n - 1));
    }

    // Step 2: Merge sorted runs
    for (int size = RUN; size < n; size *= 2) {
        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);
            }
        }
    }
}

// Utility function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

// Main function
int main() {
    int arr[] = {5, 21, 7, 23, 19, 10, 12, 3, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array:\n";
    printArray(arr, n);

    timSort(arr, n);

    cout << "Sorted array:\n";
    printArray(arr, n);

    return 0;
}

Output

Original array:
5 21 7 23 19 10 12 3 6 8 
Sorted array:
3 5 6 7 8 10 12 19 21 23 

Timsort – Visual Explanation (Step-by-Step)

Let’s sort:

[5, 21, 7, 23, 19, 10, 12, 3, 6, 8]

Step 1: Break into Runs

Array is divided into small runs of size ≤ 32:

[5, 21, 7, 23, 19, 10, 12, 3, 6, 8]

Only one run in this case → sort with Insertion Sort:

→ After insertion sort:

[3, 5, 6, 7, 8, 10, 12, 19, 21, 23]

Step 2: Merge Runs

If there were multiple runs (e.g., in larger arrays), Timsort would:

• Merge sorted runs pairwise
• Continue until one fully sorted array remains

Because we have only one small run here, no further merges are needed.

Final Sorted Array

[3, 5, 6, 7, 8, 10, 12, 19, 21, 23]

Summary

• Timsort is a hybrid of Insertion Sort and Merge Sort.
• It is fast, adaptive, and stable.
• Performs particularly well on real-world data with partial order.
• C++ does not implement Timsort by default, but it can be implemented manually as shown.