Tim Sort

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

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()

Merge()

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)

• First Iteration

Key : A[1] = 5

• Second Iteration

Key : A[2] = 4

• Third Iteration

Key: A[3] = 2

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

• First Iteration

Key : A[1] = 7

• Second Iteration

Key : A[2] = 6

• Third Iteration

Key : A[3] = 4

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.