JIYIK CN >

Tim sort is a hybrid stable sorting algorithm. It is a hybrid algorithm derived from insertion sort and merge sort . It first uses insertion sort to sort subarrays, these small sorted subarrays are called natural runs. Then merge sort is used to merge the subarrays of these runs to produce the final sorted array. It is designed keeping in mind the best performance of the algorithm on real-world data. It exploits the fact that insertion sort performs very well on small size subarrays. It is the standard sorting algorithm used by Java and Array.sort()Python .sorted()sort()

Tim sorting algorithm

Suppose we have an nunordered array containing 10 elements A[]. We will consider a run of size 10. 32It can be 2any power of 10 because 2merging is more efficient when the numbers are powers of 10.

TimSort()

1. Divide the array into n/32 runs.
2. Use the insertion sort function to sort the runs one by one.
3. Use merge sort's merge function to merge the sorted runs one by one.

Merge()

• Initialize the auxiliary array output to store the sorted output.
• Initialize three pointers i, j and k.
  • i points to the beginning of the first subarray beg.
  • j points to the beginning of the second subarray mid+1.
  • k is initialized with beg and holds the current index into the sorted array output.
• Until we reach the end of the arr[beg, .... ,mid]or arr[mid+1, .... ,end]subarray, we i&jpick a smaller value from the element at index and insert it into output.
• When one of the arrays is exhausted, the remaining elements are picked and inserted into the output.
• Copy output into arr[beg, ... , end].

Tim Sorting Example

Suppose we have the array: (3, 5, 2, 8, 1, 7, 6, 4). We will sort it using Tim's sorting algorithm. To keep the explanation simple, let's consider the size of the run to be 4.

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

First subarray:(3, 5, 2, 8)

• First Iteration

Key: A[1]=5

• Second Iteration

Key: A[2]=4

• Third iteration

Key: A[3]=2

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 two sorted subarrays and the final subarray is: (1, 2, 3, 4, 5, 6, 7, 8).

Implementation of Tim's sorting algorithm

#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's sorting algorithm complexity

Time Complexity

• Average situation

This algorithm requires O(nlogn)comparisons to nsort an array of elements. Therefore, the time complexity is [Big Theta]: O(nlogn).

• Worst case scenario

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

• Best Case

The best case is when the array is already sorted and no swapping is needed. The time complexity for the best case is [Big Omega]: O(n).

Space complexity

The space complexity of this algorithm is O(n)because the merge sort algorithm requires additional auxiliary space O(n).