Tim Sort
Hybrid sorting algorithm derived from merge sort and insertion sort. Python's built-in sort and Java's Arrays.sort. Invented by Tim Peters in 2002. Exploits runs of consecutive sorted elements.
Visualization
Interactive visualization for Tim Sort
Tim Sort Visualization
Hybrid sorting combining insertion sort for small runs and merge sort
Algorithm: Tim Sort (Python's default)
Run Size: 32
Steps: 0
How it works:
- Divide array into runs of size 32
- Sort each run using insertion sort
- Merge runs using merge sort strategy
- Exploits natural runs in real-world data
Interactive visualization with step-by-step execution
Implementation
1const MIN_RUN = 32;
2
3function getMinRun(n: number): number {
4 let r = 0;
5 while (n >= MIN_RUN) {
6 r |= n & 1;
7 n >>= 1;
8 }
9 return n + r;
10}
11
12function insertionSort(arr: number[], left: number, right: number): void {
13 for (let i = left + 1; i <= right; i++) {
14 const key = arr[i];
15 let j = i - 1;
16 while (j >= left && arr[j] > key) {
17 arr[j + 1] = arr[j];
18 j--;
19 }
20 arr[j + 1] = key;
21 }
22}
23
24function merge(arr: number[], l: number, m: number, r: number): void {
25 const left = arr.slice(l, m + 1);
26 const right = arr.slice(m + 1, r + 1);
27
28 let i = 0, j = 0, k = l;
29
30 while (i < left.length && j < right.length) {
31 if (left[i] <= right[j]) {
32 arr[k++] = left[i++];
33 } else {
34 arr[k++] = right[j++];
35 }
36 }
37
38 while (i < left.length) arr[k++] = left[i++];
39 while (j < right.length) arr[k++] = right[j++];
40}
41
42function timSort(arr: number[]): number[] {
43 const sorted = [...arr];
44 const n = sorted.length;
45 const minRun = getMinRun(n);
46
47 // Sort individual runs
48 for (let start = 0; start < n; start += minRun) {
49 const end = Math.min(start + minRun - 1, n - 1);
50 insertionSort(sorted, start, end);
51 }
52
53 // Merge runs
54 let size = minRun;
55 while (size < n) {
56 for (let start = 0; start < n; start += 2 * size) {
57 const mid = start + size - 1;
58 const end = Math.min(start + 2 * size - 1, n - 1);
59
60 if (mid < end) {
61 merge(sorted, start, mid, end);
62 }
63 }
64 size *= 2;
65 }
66
67 return sorted;
68}Deep Dive
Theoretical Foundation
Divides array into small chunks called 'runs' (min 32-64 elements). Sorts runs using insertion sort. Merges runs using merge sort strategy. Highly optimized for real-world data with partial ordering. Stable and adaptive.
Complexity
Time
O(n)
O(n log n)
O(n log n)
Space
O(n)
Applications
Use Cases
Related Algorithms
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.
Merge Sort
A stable, divide-and-conquer sorting algorithm with guaranteed O(n log n) performance.
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. This process is repeated until the entire array is sorted. Named for the way larger elements 'bubble' to the top (end) of the array.
Insertion Sort
Insertion Sort is a simple, intuitive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how people sort playing cards in their hands - picking each card and inserting it into its correct position among the already sorted cards. Despite its O(n²) time complexity, Insertion Sort is efficient for small datasets and nearly sorted arrays, making it practical for real-world applications.