what is Tim-sort?

Tim-sort

Tim-sort is a sorting algorithm derived from insertion sort and merge sort. It was designed to perform in an optimal way on different kind of real world data. It is an adaptive sorting algorithm which needs O(n log n) comparisons to sort an array of n elements. It was designed and implemented by Tim Peters in 2002 in python programming language. It has been python's standard sorting algorithm since version 2.3.

Technique

Consider an array of n elements which needs to be sorted. In Tim sort, the array is divided into several parts where each of them is called a Run. These Runs are sorted by using insertion sort one by one and then the sorted runs get combined using a combine function. The idea of Tim sort is originated from the fact that, insertion sort works more optimally on the short lists rather than working on the larger lists.

Complexity

Complexity	Best Case	Average Case	Worst Case
Time Complexity	O(n)	O(n log n)	O(n log n)
Space Complexity			n

Steps :

1. Divide the array into the number of blocks known as run.
2. Consider size of run either 32 or 64(in the below implementation, size of run is 32.)
3. Sort the individual elements of every run one by one using insertion sort.
4. Merge the sorted runs one by one using merge function of merge sort.
5. Double the size of merged sub-arrays after every iteration.

C program

1. #include<stdio.h>  
2. const int run = 32;  
3. int minimum(int a, int b)  
4. {  
5.     if(a<b)  
6.     return a;   
7.     else   
8.     return b;   
9. }  
10. void insertionSort(int a[], int beg, int end)  
11. {  
12.     int temp, i, j;   
13.     for (i = beg + 1; i <= end; i++)  
14.     {  
15.         temp = a[i];  
16.         j = i - 1;  
17.         while (a[j] > temp && j >= beg)  
18.         {  
19.             a[j+1] = a[j];  
20.             j--;  
21.         }  
22.         a[j+1] = temp;  
23.     }  
24. }  
25.    
26. void merge(int a[], int left, int mid, int right)  
27. {  
28.     int len1 = mid - left + 1, len2 = right - mid;  
29.     int beg[len1], end[len2];  
30.     int i,j,k;  
31.     for (i = 0; i < len1; i++)  
32.         beg[i] = a[left + i];  
33.     for (i = 0; i < len2; i++)  
34.         end[i] = a[mid + 1 + i];  
35.    
36.     i = 0;  
37.     j = 0;  
38.     k = left;  
39.    
40.     while (i < len1 && j < len2)  
41.     {  
42.         if (beg[i] <= end[j])  
43.         {  
44.             a[k] = beg[i];  
45.             i++;  
46.         }  
47.         else  
48.         {  
49.             a[k] = end[j];  
50.             j++;  
51.         }  
52.         k++;  
53.     }  
54.     while (i < len1)  
55.     {  
56.         a[k] = beg[i];  
57.         k++;  
58.         i++;  
59.     }  
60.    
61.     while (j < len2)  
62.     {  
63.         a[k] = end[j];  
64.         k++;  
65.         j++;  
66.     }  
67. }  
68. void timSort(int a[], int n)  
69. {  
70.     int i,size,beg,mid,end;  
71.     for (i = 0; i < n; i+=run)  
72.         insertionSort(a, i, minimum((i+31), (n-1)));  
73.     for (size = run; size < n; size = 2*size)  
74.     {  
75.         for (beg = 0; beg < n; beg += 2*size)  
76.         {  
77.             mid = beg + size - 1;  
78.             end = minimum((beg + 2*size - 1), (n-1));  
79.    
80.             merge(a, beg, mid, end);  
81.         }  
82.     }  
83. }  
84.   
85. int main()  
86. {  
87.     int a[] = {12,1,20,2,3,123,54,332},i;  
88.     int n = sizeof(a)/sizeof(a[0]);  
89.     printf("Printing Array elements \n");  
90.     for (i = 0; i < n; i++)  
91.     printf("%d  ", a[i]);  
92.     printf("\n");  
93.     timSort(a, n);  
94.    
95.     printf("Printing sorted array elements \n");  
96.     for (i = 0; i < n; i++)  
97.         printf("%d  ", a[i]);  
98.     printf("\n");  
99.     return 0;  
100. }  
Output:


Printing Array elements 
12  1  20  2  3  123  54  332
  
Printing sorted array elements 
1  2  3  12  20  54  123  332