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