Tim Sort is a highly optimized hybrid sorting algorithm designed for real-world data. It divides the array into small runs (typically 32-64 elements) sorted with Insertion Sort, then merges those runs using an optimized merge procedure. It leverages existing order in the data and achieves O(n) on already-sorted or reverse-sorted input.
const int RUN = 32;
void insertionSortRun(vector<int>& arr, int l, int r) {
for (int i = l+1; i <= r; i++) {
int key = arr[i], j = i-1;
while (j >= l && arr[j] > key) { arr[j+1]=arr[j]; j--; }
arr[j+1] = key;
}
}
void merge(vector<int>& arr, int l, int m, int r) {
vector<int> L(arr.begin()+l,arr.begin()+m+1), R(arr.begin()+m+1,arr.begin()+r+1);
int i=0,j=0,k=l;
while(i<L.size()&&j<R.size()) arr[k++]=L[i]<=R[j]?L[i++]:R[j++];
while(i<L.size()) arr[k++]=L[i++];
while(j<R.size()) arr[k++]=R[j++];
}
void timSort(vector<int>& arr) {
int n=arr.size();
for(int i=0;i<n;i+=RUN) insertionSortRun(arr,i,min(i+RUN-1,n-1));
for(int size=RUN;size<n;size*=2)
for(int l=0;l<n;l+=2*size) {
int m=min(l+size-1,n-1), r=min(l+2*size-1,n-1);
if(m<r) merge(arr,l,m,r);
}
}Real-world data often has natural runs of already-sorted elements. Tim Sort exploits these runs rather than treating all data as random. It was designed by Tim Peters for Python in 2002 and is now the default sort in Python, Java, and Swift.
Tim Sort divides the array into minimum-run-sized chunks (typically 32) and sorts each with Insertion Sort. Insertion Sort has very low overhead for small arrays and leverages existing order within each chunk.
After sorting individual runs, Tim Sort merges them in a balanced fashion similar to Merge Sort. It uses a stack to track pending runs and applies merge rules to keep the merge tree balanced.
When one run dominates during merging (many consecutive elements from same run win), Tim Sort switches to galloping mode — binary searching for where to switch — drastically reducing comparisons for partially-sorted data.
Quiz coming soon for this algorithm.