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
