Tim Sort
A hybrid stable sorting algorithm derived from merge sort and insertion sort, designed to perform well on real-world data. It is the default sorting algorithm in Python and Java.
Visualization
Details
Analogy
Imagine organizing a large library. Instead of sorting all books at once, you first divide them into small sections (runs) and sort each section using a simple method (insertion sort). Then you progressively merge these sorted sections, like combining sorted card decks. This hybrid approach is much faster than using one method throughout, especially when some sections are already organized.
Purpose
To efficiently sort data by leveraging the strengths of both insertion sort (for small subarrays) and merge sort (for larger datasets). Tim Sort identifies and exploits existing order in the data, making it exceptionally fast on partially sorted or real-world datasets.
Use Cases
Default sorting algorithm in Python (list.sort() and sorted()), Java (Arrays.sort() for objects), and Android. Ideal for real-world data which often has naturally ordered sequences. Excellent for large datasets, especially those that are partially sorted. Used in production systems where reliability and performance on varied inputs is critical.
Algorithm Steps
function timSort(array):
RUN = 32
n = length(array)
for start = 0 to n step RUN:
end = min(start + RUN - 1, n - 1)
insertionSort(array, start, end)
size = RUN
while size < n:
for start = 0 to n step 2 * size:
mid = start + size - 1
end = min(start + 2 * size - 1, n - 1)
if mid < end:
merge(array, start, mid, end)
size = size * 2
return array
Explanation
What's Happening?
Initial array: [5, 21, 7, 23, 19, 3, 16, 8]. Tim Sort uses RUN size of 32 (or array size if smaller).
Code Implementation
def insertion_sort(arr, left, right):
for i in range(left + 1, right + 1):
key = arr[i]
j = i - 1
while j >= left and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
def merge(arr, left, mid, right):
left_part = arr[left:mid + 1]
right_part = arr[mid + 1:right + 1]
i = j = 0
k = left
while i < len(left_part) and j < len(right_part):
if left_part[i] <= right_part[j]:
arr[k] = left_part[i]
i += 1
else:
arr[k] = right_part[j]
j += 1
k += 1
while i < len(left_part):
arr[k] = left_part[i]
i += 1
k += 1
while j < len(right_part):
arr[k] = right_part[j]
j += 1
k += 1
def tim_sort(arr):
RUN = 32
n = len(arr)
for start in range(0, n, RUN):
end = min(start + RUN - 1, n - 1)
insertion_sort(arr, start, end)
size = RUN
while size < n:
for start in range(0, n, 2 * size):
mid = start + size - 1
end = min(start + 2 * size - 1, n - 1)
if mid < end:
merge(arr, start, mid, end)
size *= 2
return arr