Tim Sort

  1. Tim Sort Algorithm
  2. Tim Sort Example
  3. Tim Sort Algorithm Implementation
  4. Tim Sort Algorithm Complexity
Note

If you don’t know what insertion sort and merge sort are, please go through the insertion sort and merge sort articles first.

Tim sort is a hybrid stable sorting algorithm. It is a hybrid algorithm derived from insertion sort and merge sort. It first subarrays using insertion sort; these small sorted subarrays are called natural runs. These runs are then merged subarray using merge sort to produce final sorted arrays. It is designed keeping in mind the optimal performance of the algorithm on real-world data. It uses the fact that insertion sort performs really well on small-sized subarrays. It is the standard sorting algorithm used by Java’s Array.sort() and Python’s sorted() and sort().

Tim Sort Algorithm

Let us assume that we have an unsorted array A[] containing n elements. We will consider the size of the run as 32. It can be any power of 2 because merging is more effective when numbers are of powers of 2.

TimSort()

  • Divide the array into n/32 runs.
  • Sort individual runs using insertion sort one by one.
  • Merge the sorted runs one by one using the merge function of merge sort.

Merge()

  • Initialize the auxiliary array output to store the sorted output.
  • Initialize 3 pointers i, j & k.

    i points to the beginning of the first subarray beg.
    j points to the beginning of the second subarray mid+1.
    k initialized with beg maintains the current index of sorted array output.

  • Until we reach the end of arr[beg, .... ,mid] or arr[mid+1, .... ,end] subarray, we pick the smaller value among elements at index i &j and insert into output.
  • Pick the remaining elements and insert them into output once one of the arrays is exhausted.
  • Copy output into arr[beg, ... , end].

Tim Sort Example

Suppose we have the array: (3, 5, 2, 8, 1, 7, 6, 4). We will sort it using the Tim sort algorithm. To keep the illustration simple, let us consider the size of the run as 4.

Divide the array into two subarrays: (3, 5, 2, 8) and (1, 7, 6, 4).

The first subarray: (3, 5, 2, 8)

Sorted subarray Unsorted Subarray Array
(3) (5, 2, 8) (3,5,2,8)
  • First Iteration

Key : A[1] = 5

Sorted subarray Unsorted Subarray Array
( 3 , 5) (2, 8) (3, 5, 2, 8)
  • Second Iteration

Key : A[2] = 4

Sorted subarray Unsorted Subarray Array
( 2, 3, 5) (8) (2, 3, 5, 8)
  • Third Iteration

Key: A[3] = 2

Sorted subarray Unsorted Subarray Array
( 2, 3, 5, 8) () (2, 3, 5, 8)

The second subarray:(1,7,6,4)

Sorted subarray Unsorted Subarray Array
(1) (7, 6, 4) (1, 7, 6, 4)
  • First Iteration

Key : A[1] = 7

Sorted subarray Unsorted Subarray Array
( 1 , 7) (6, 4) (1, 7, 6, 4)
  • Second Iteration

Key : A[2] = 6

Sorted subarray Unsorted Subarray Array
( 1, 6, 7) (4) (1, 6, 7, 4)
  • Third Iteration

Key : A[3] = 4

Sorted subarray Unsorted Subarray Array
( 1, 4, 6, 7) () (1, 4, 6, 7)

Merge the two sorted subarrays to get the final subarray as: (1, 2, 3, 4, 5, 6, 7, 8)

Tim Sort Algorithm Implementation

#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 beg, int mid, int end) {
    int output[end - beg + 1];
    int i = beg, j = mid + 1, k = 0;
    // add smaller of both elements to the output
    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) {
            output[k] = arr[i];
            k += 1; i += 1;
        }
        else {
            output[k] = arr[j];
            k += 1; j += 1;
        }
    }
    // remaining elements from first array
    while (i <= mid) {
        output[k] = arr[i];
        k += 1; i += 1;
    }
    // remaining elements from the second array
    while (j <= end) {
        output[k] = arr[j];
        k += 1; j += 1;
    }
    // copy output to the original array
    for (i = beg; i <= end; i += 1) {
        arr[i] = output[i - beg];
    }
    }
void timSort(int arr[], int n)
{

    for (int i = 0; i < n; i += RUN)
        insertionSort(arr, i, min((i + 31),
                                  (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));

            merge(arr, left, mid, right);
        }
    }
}

int main() {

    int n = 6;
    int arr[6] = {5, 3, 4, 2, 1, 6};
    cout << "Input array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    timSort(arr, n); // Sort elements in ascending order
    cout << "Output array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

Tim Sort Algorithm Complexity

Time Complexity

  • Average Case

The algorithm requires O(nlogn) comparisons to sort an array of n elements. Hence, the time complexity is of the order of [Big Theta]: O(nlogn).

  • Worst Case

In worst-case, nlogn comparisons are required. The worst-case time complexity is [Big O]: O(nlogn). It is the same as average-case time complexity.

  • Best Case

The best-case occurs when the array is already sorted, and no swaps are required. The best-case time complexity is [Big Omega]: O(n).

Space Complexity

Space Complexity for this algorithm is O(n) because extra auxiliary space of O(n) is required by the merge sort algorithm.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

Related Article - Sort Algorithm

  • Binary Sort
  • Insertion Sort