Tim Sort is a highly efficient sorting algorithm that combines ideas from merge sort and insertion sort. It was originally designed to handle real-world data efficiently, taking advantage of already-sorted sequences in arrays. The main concept is to divide the array into small segments called “runs,” sort each run using insertion sort, and then merge these runs using merge sort techniques. For Rust programmers, implementing Tim Sort is a great way to practice array handling, slices, and both iterative and recursive programming concepts.
with hands-on learning.
get the skills and confidence to land your next move.
Tim Sort is widely used in programming languages and libraries, including Python’s built-in sort and Java’s Arrays.sort. It excels at sorting arrays that are partially sorted, making it faster than other O(n log n) algorithms in practical situations. Beginners can learn a lot from Tim Sort because it demonstrates combining two different sorting strategies and shows how hybrid algorithms can efficiently handle complex data.
Program 1: Basic Tim Sort Using Fixed Run Size
This program demonstrates Tim Sort using a small, fixed run size. Each run is sorted with insertion sort, and runs are merged iteratively.
fn insertion_sort(arr: &mut [i32], left: usize, right: usize) {
for i in (left + 1)..=right {
let key = arr[i];
let mut j = i;
while j > left && arr[j - 1] > key {
arr[j] = arr[j - 1];
j -= 1;
}
arr[j] = key;
}
}
fn merge(arr: &mut [i32], l: usize, m: usize, r: usize) {
let left_slice = arr[l..=m].to_vec();
let right_slice = arr[(m + 1)..=r].to_vec();
let mut i = 0;
let mut j = 0;
let mut k = l;
while i < left_slice.len() && j < right_slice.len() {
if left_slice[i] <= right_slice[j] {
arr[k] = left_slice[i];
i += 1;
} else {
arr[k] = right_slice[j];
j += 1;
}
k += 1;
}
while i < left_slice.len() {
arr[k] = left_slice[i];
i += 1;
k += 1;
}
while j < right_slice.len() {
arr[k] = right_slice[j];
j += 1;
k += 1;
}
}
fn tim_sort(arr: &mut [i32], run: usize) {
let n = arr.len();
for i in (0..n).step_by(run) {
let end = if i + run - 1 < n { i + run - 1 } else { n - 1 };
insertion_sort(arr, i, end);
}
let mut size = run;
while size < n {
let mut left = 0;
while left < n {
let mid = if left + size - 1 < n { left + size - 1 } else { n - 1 };
let right = if left + 2 * size - 1 < n { left + 2 * size - 1 } else { n - 1 };
if mid < right {
merge(arr, left, mid, right);
}
left += 2 * size;
}
size *= 2;
}
}
fn main() {
let mut numbers = [37, 23, 0, 17, 12, 72, 31, 46, 100, 5];
println!("Original array: {:?}", numbers);
tim_sort(&mut numbers, 4);
println!("Sorted array: {:?}", numbers);
}This example introduces the basic structure of Tim Sort. Runs are sorted individually, then merged. Beginners can see how insertion sort and merge sort combine to create a hybrid sorting algorithm.
Program 2: Tim Sort with Dynamic Run Size
This program calculates an optimal run size based on the array length, making the algorithm more flexible.
fn insertion_sort(arr: &mut [i32], left: usize, right: usize) {
for i in (left + 1)..=right {
let key = arr[i];
let mut j = i;
while j > left && arr[j - 1] > key {
arr[j] = arr[j - 1];
j -= 1;
}
arr[j] = key;
}
}
fn merge(arr: &mut [i32], l: usize, m: usize, r: usize) {
let left_slice = arr[l..=m].to_vec();
let right_slice = arr[(m + 1)..=r].to_vec();
let mut i = 0;
let mut j = 0;
let mut k = l;
while i < left_slice.len() && j < right_slice.len() {
if left_slice[i] <= right_slice[j] {
arr[k] = left_slice[i];
i += 1;
} else {
arr[k] = right_slice[j];
j += 1;
}
k += 1;
}
while i < left_slice.len() {
arr[k] = left_slice[i];
i += 1;
k += 1;
}
while j < right_slice.len() {
arr[k] = right_slice[j];
j += 1;
k += 1;
}
}
fn tim_sort(arr: &mut [i32], run: usize) {
let n = arr.len();
for i in (0..n).step_by(run) {
let end = if i + run - 1 < n { i + run - 1 } else { n - 1 };
insertion_sort(arr, i, end);
}
let mut size = run;
while size < n {
let mut left = 0;
while left < n {
let mid = if left + size - 1 < n { left + size - 1 } else { n - 1 };
let right = if left + 2 * size - 1 < n { left + 2 * size - 1 } else { n - 1 };
if mid < right {
merge(arr, left, mid, right);
}
left += 2 * size;
}
size *= 2;
}
}
fn min_run_length(n: usize) -> usize {
let mut r = 0;
let mut n = n;
while n >= 32 {
r |= n & 1;
n >>= 1;
}
n + r
}
fn tim_sort_dynamic(arr: &mut [i32]) {
let n = arr.len();
let run = min_run_length(n);
tim_sort(arr, run);
}
fn main() {
let mut numbers = [10, 21, 3, 44, 2, 7, 12, 9, 0, 33];
println!("Original array: {:?}", numbers);
tim_sort_dynamic(&mut numbers);
println!("Sorted array: {:?}", numbers);
}Dynamic run size demonstrates a practical optimization. Beginners learn that hybrid algorithms can adapt parameters for better performance depending on input size.
Program 3: Tim Sort for Floating-Point Arrays
Here, Tim Sort is adapted to handle floating-point numbers efficiently.
fn tim_sort_floats(arr: &mut [f64], run: usize) {
let n = arr.len();
for i in (0..n).step_by(run) {
let end = if i + run - 1 < n { i + run - 1 } else { n - 1 };
insertion_sort_float(arr, i, end);
}
let mut size = run;
while size < n {
let mut left = 0;
while left < n {
let mid = if left + size - 1 < n { left + size - 1 } else { n - 1 };
let right = if left + 2 * size - 1 < n { left + 2 * size - 1 } else { n - 1 };
if mid < right {
merge_float(arr, left, mid, right);
}
left += 2 * size;
}
size *= 2;
}
}
fn insertion_sort_float(arr: &mut [f64], left: usize, right: usize) {
for i in (left + 1)..=right {
let key = arr[i];
let mut j = i;
while j > left && arr[j - 1] > key {
arr[j] = arr[j - 1];
j -= 1;
}
arr[j] = key;
}
}
fn merge_float(arr: &mut [f64], l: usize, m: usize, r: usize) {
let left_slice = arr[l..=m].to_vec();
let right_slice = arr[(m + 1)..=r].to_vec();
let mut i = 0;
let mut j = 0;
let mut k = l;
while i < left_slice.len() && j < right_slice.len() {
if left_slice[i] <= right_slice[j] {
arr[k] = left_slice[i];
i += 1;
} else {
arr[k] = right_slice[j];
j += 1;
}
k += 1;
}
while i < left_slice.len() {
arr[k] = left_slice[i];
i += 1;
k += 1;
}
while j < right_slice.len() {
arr[k] = right_slice[j];
j += 1;
k += 1;
}
}
fn main() {
let mut numbers = [3.2, 1.5, 0.9, 7.8, 2.1, 4.3];
println!("Original array: {:?}", numbers);
tim_sort_floats(&mut numbers, 4);
println!("Sorted array: {:?}", numbers);
}Adapting to floats shows the algorithm’s versatility. Beginners see that sorting logic is generalizable beyond integers.
Program 4: Tim Sort with Debug Printing
This version prints the array after each merge step to help visualize the algorithm.
fn insertion_sort(arr: &mut [i32], left: usize, right: usize) {
for i in (left + 1)..=right {
let key = arr[i];
let mut j = i;
while j > left && arr[j - 1] > key {
arr[j] = arr[j - 1];
j -= 1;
}
arr[j] = key;
}
}
fn merge(arr: &mut [i32], l: usize, m: usize, r: usize) {
let left_slice = arr[l..=m].to_vec();
let right_slice = arr[(m + 1)..=r].to_vec();
let mut i = 0;
let mut j = 0;
let mut k = l;
while i < left_slice.len() && j < right_slice.len() {
if left_slice[i] <= right_slice[j] {
arr[k] = left_slice[i];
i += 1;
} else {
arr[k] = right_slice[j];
j += 1;
}
k += 1;
}
while i < left_slice.len() {
arr[k] = left_slice[i];
i += 1;
k += 1;
}
while j < right_slice.len() {
arr[k] = right_slice[j];
j += 1;
k += 1;
}
}
fn tim_sort_debug(arr: &mut [i32], run: usize) {
let n = arr.len();
for i in (0..n).step_by(run) {
let end = if i + run - 1 < n { i + run - 1 } else { n - 1 };
insertion_sort(arr, i, end);
}
let mut size = run;
while size < n {
let mut left = 0;
while left < n {
let mid = if left + size - 1 < n { left + size - 1 } else { n - 1 };
let right = if left + 2 * size - 1 < n { left + 2 * size - 1 } else { n - 1 };
if mid < right {
merge(arr, left, mid, right);
println!("Array after merging from {} to {}: {:?}", left, right, arr);
}
left += 2 * size;
}
size *= 2;
}
}
fn main() {
let mut numbers = [20, 35, 15, 40, 10, 5, 25];
println!("Original array: {:?}", numbers);
tim_sort_debug(&mut numbers, 3);
println!("Sorted array: {:?}", numbers);
}Debugging output helps beginners see how merging progressively sorts larger segments of the array.
Program 5: Recursive Tim Sort Implementation
This example shows a recursive approach for merging runs, illustrating another way to implement Tim Sort.
fn merge(arr: &mut [i32], l: usize, m: usize, r: usize) {
let left_slice = arr[l..=m].to_vec();
let right_slice = arr[(m + 1)..=r].to_vec();
let mut i = 0;
let mut j = 0;
let mut k = l;
while i < left_slice.len() && j < right_slice.len() {
if left_slice[i] <= right_slice[j] {
arr[k] = left_slice[i];
i += 1;
} else {
arr[k] = right_slice[j];
j += 1;
}
k += 1;
}
while i < left_slice.len() {
arr[k] = left_slice[i];
i += 1;
k += 1;
}
while j < right_slice.len() {
arr[k] = right_slice[j];
j += 1;
k += 1;
}
}
fn tim_sort_recursive(arr: &mut [i32], run: usize, left: usize, right: usize) {
if left >= right {
return;
}
let mid = (left + right) / 2;
tim_sort_recursive(arr, run, left, mid);
tim_sort_recursive(arr, run, mid + 1, right);
merge(arr, left, mid, right);
}
fn main() {
let mut numbers = [34, 7, 23, 32, 5, 62];
println!("Original array: {:?}", numbers);
let size = numbers.len();
tim_sort_recursive(&mut numbers, 4, 0, size - 1);
println!("Sorted array: {:?}", numbers);
}This recursive version reinforces understanding of how merging works and shows that Tim Sort can be implemented both iteratively and recursively.
Frequently Asked Questions (FAQ)
Q1: Why is Tim Sort considered efficient?
Tim Sort leverages existing sorted sequences in data, reducing the number of comparisons and merges required, which makes it very fast on real-world datasets.
Q2: Can Tim Sort handle different data types?
Yes, with proper comparisons, it can sort integers, floats, strings, and other comparable types.
Q3: What is a “run” in Tim Sort?
A run is a contiguous segment of the array that is sorted using insertion sort before merging.
Q4: Is Tim Sort stable?
Yes, Tim Sort is stable, preserving the relative order of equal elements.
Q5: How does Tim Sort compare with quicksort?
Tim Sort is generally more efficient on partially sorted arrays and is stable, whereas quicksort is faster for completely random large arrays but not stable.
Conclusion
Implementing Tim Sort in Rust introduces beginners to hybrid algorithms that combine insertion sort and merge sort. By experimenting with fixed and dynamic run sizes, floats, debug-friendly outputs, and recursive approaches, beginners can understand both the mechanics and flexibility of the algorithm. Practicing Tim Sort reinforces key programming concepts like array manipulation, loops, recursion, and the power of hybrid sorting methods. With these examples, learners can confidently handle practical sorting challenges while gaining deeper insight into Rust programming.
