Timsort

TimSort Time Complexity

Timsort is a sorting algorithm that is quite efficient for real-world data. Timsort is created in 2001 by Tim Peters for the python programming language. Timsort is a hybrid stable sorting algorithm and it is the combination of Insertion Sort and Marge Sort. After it has been created, it is used in java’s Arrays.sort() as well as python’s sorted() and sort().

How it works

In Tim sort, we divide the Array or List into blocks. Then, after we use insertion sort to sort those blocks one by one and then, by the help of merge function of merge sort, we combine or merge those blocks. The concept behind is that the insertion sort performs well for small arrays.

Timsort time complexity comparison

Algorithm		Time Complexity
	Best-Case	Average-Case          Worst-Case
Tim Sort	O(n)	O(n log( n ) )                   O(n log( n ) )
Quick Sort	O(n log( n ) )	O(n log( n ) )                   O(n^2)
Merge Sort	O(n log( n ) )	O(n log( n ) )                   O(n log( n ) )

Timsort program in C-language: -

 #include<stdio.h>
 #define BLOCK 32
 void insertion_Sort(int array[], int lt, int rgt)
 {
     int i=0;
     for ( i = lt + 1; i <= rgt; i++)
     {
         int temp_var = array[i];
         int j = i - 1;
         while (array[j] > temp_var && j >= lt)
         {
             array[j+1] = array[j];
             j--;
         }
         array[j+1] = temp_var;
     }
 }
 // merge function
 void merge(int array[], int l, int m, int r)
 {
     // we divide array into two part left and right array
     int len1 = m - l + 1, len2 = r - m,i=0;
     int lt[len1], rgt[len2];
     for ( i = 0; i < len1; i++)
         lt[i] = array[l + i];
     for ( i = 0; i < len2; i++)
         rgt[i] = array[m + 1 + i];
     i = 0;
     int j = 0;
     int k = l;
     // after that, we combine those two sub-arrays
     while (i < len1 && j < len2)
     {
         if (lt[i] <= rgt[j])
         {
             array[k] = lt[i];
             i++;
         }
         else
         {
             array[k] = rgt[j];
             j++;
         }
         k++;
     }
     // we copy remaining left array element
     while (i < len1)
     {
         array[k] = lt[i];
         k++;
         i++;
     }
     // we copy remaining right array element
     while (j < len2)
     {
         array[k] = rgt[j];
         k++;
         j++;
     }
 }
 int min(int a,int b)
 {
     if(a<b)
         return a;
     return b;
 }
 void tim_Sort(int array[], int n)
 {
     // Sort individual subarrays of size BLOCK
     int i=0,size=0,lt=0;
     for ( i = 0; i < n; i+=BLOCK)
         insertion_Sort(array, i, min((i+31), (n-1)));
     for (size = BLOCK; size < n; size = 2*size)
     {
         // After every merge, we increase lt by 2*size
         for ( lt = 0; lt < n; lt += 2*size)
         {
             int mid = lt + size - 1;
             int rgt = min((lt + 2*size - 1), (n-1));
             // merge sub array array[lt.....mid] & array[mid+1..A..rgt]
             merge(array, lt, mid, rgt);
         }
     }
 }
 // For printing the array
 void printArray(int array[], int n)
 {
     int i=0;
     for ( i = 0; i < n; i++)
         printf("%d  ", array[i]);
     printf("\n");
 }
 // Driver function
 int main()
 {
     int array[] = {5, 21, 7, 23, 19};
     int n = sizeof(array)/sizeof(array[0]);
     printf("Given Array is\n");
     printArray(array, n);
     tim_Sort(array, n);
     printf("After Sorting Array is\n");
     printArray(array, n);
     return 0;
 } 

Output