How To Do TimSort in Rust

TimSort is a hybrid sorting algorithm derived from Merge Sort and Insertion Sort. It was designed to perform efficiently on real-world data, which often contains ordered sequences or runs—consecutive elements that are already sorted. TimSort excels in scenarios where the dataset is partially sorted or contains recognizable patterns.

TimSort is the default sorting algorithm used in popular languages like Python and JavaScript (in modern engines like V8). It combines the stable and predictable performance of Merge Sort with the fast handling of small arrays using Insertion Sort. In this blog post, we will explore how TimSort works, its Rust implementation, and why it performs so well in many practical use cases.

What Is TimSort

TimSort was developed by Tim Peters in 2002 for Python and is now widely used in JavaScript’s Array.prototype.sort() method in most modern engines. The algorithm identifies small segments of the array, called runs, that are already sorted. It then uses Insertion Sort to sort small arrays and Merge Sort to combine the runs. This makes it highly efficient when the data has a lot of existing order or partial sorting.

TimSort is designed to minimize the number of comparisons and swaps, making it faster than typical comparison-based algorithms like Quick Sort or Merge Sort in many real-world applications.

How TimSort Works

TimSort’s main idea is to exploit the natural order of real-world data. It does this by:

1. Identifying Runs: Finding sections of the array that are already sorted (ascending or descending).
2. Sorting Small Runs: Using Insertion Sort for small sections (or runs) to minimize overhead.
3. Merging Runs: Efficiently merging these runs using Merge Sort ensures that the sorting is stable and efficient.

Key Concepts:

• Runs: A run is a contiguous sequence of already sorted elements. TimSort scans the array to detect these runs.
• MinRun: The MinRun is the minimum size of runs that TimSort creates. TimSort uses Insertion Sort for small arrays (smaller than MinRun).

Pseudocode for TimSort

procedure TimSort(arr)
    n = length of arr
    minRun = calculateMinRun(n)

    # Step 1: Sort small sub-arrays using Insertion Sort
    for i = 0 to n - 1 in steps of minRun do
        InsertionSort(arr, i, min(i + minRun - 1, n - 1))

    # Step 2: Merge sorted runs using Merge Sort
    size = minRun
    while size < n do
        for left = 0 to n - 1 in steps of 2 * size do
            mid = min(left + size - 1, n - 1)
            right = min(left + 2 * size - 1, n - 1)
            if mid < right:
                Merge(arr, left, mid, right)
        size = 2 * size

Step-by-Step Explanation:

• Step 1: The array is divided into smaller runs, and each run is sorted using Insertion Sort. The minimum size of each run is determined dynamically.
• Step 2: The sorted runs are merged using Merge Sort, gradually increasing the size of the sorted portions until the entire array is sorted.

Time Complexity of TimSort

• Best Case: O(n)—TimSort performs best with linear time complexity when the input array is already sorted.
• Average Case: O(n log n) – TimSort performs at O(n log n) for most inputs, similar to other efficient sorting algorithms.
• Worst Case: O(n log n) – Even in the worst-case scenario, TimSort guarantees O(n log n) time complexity due to its merging process.

Space Complexity of TimSort

• Space Complexity: O(n) – TimSort requires additional space for merging, as it uses a temporary array during the merge step.

Rust Implementation of TimSort

Here’s the Rust code to implement TimSort:

// Insertion Sort for small runs
fn insertion_sort<T: Ord + Clone>(arr: &mut [T]) {
    for i in 1..arr.len() {
        let key = arr[i].clone(); // Clone the element to avoid moving it
        let mut j = i;

        while j > 0 && arr[j - 1] > key {
            arr[j] = arr[j - 1].clone(); // Shift the element
            j -= 1;
        }
        arr[j] = key; // Insert the element at the correct position
    }
}


// Merge function for merging sorted runs
fn merge<T: Ord + Clone>(left: &mut [T], right: &mut [T], arr: &mut [T]) {
    let (mut i, mut j, mut k) = (0, 0, 0);

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            arr[k] = left[i].clone();
            i += 1;
        } else {
            arr[k] = right[j].clone();
            j += 1;
        }
        k += 1;
    }

    while i < left.len() {
        arr[k] = left[i].clone();
        i += 1;
        k += 1;
    }

    while j < right.len() {
        arr[k] = right[j].clone();
        j += 1;
        k += 1;
    }
}

// Calculate minimum run size
fn calculate_min_run(n: usize) -> usize {
    let mut r = 0;
    let mut n = n;
    while n >= 64 {
        r |= n & 1;
        n >>= 1;
    }
    n + r
}

// Timsort implementation
fn timsort<T: Ord + Clone>(arr: &mut [T]) {
    let min_run = calculate_min_run(arr.len());

    // Step 1: Sort small runs using Insertion Sort
    let mut i = 0;
    while i < arr.len() {
        let run_end = usize::min(i + min_run, arr.len());
        insertion_sort(&mut arr[i..run_end]);
        i = run_end;
    }

    // Step 2: Merge sorted runs
    let mut size = min_run;
    while size < arr.len() {
        for start in (0..arr.len()).step_by(2 * size) {
            let mid = usize::min(start + size, arr.len());
            let end = usize::min(start + 2 * size, arr.len());

            if mid < end {
                let mut left = arr[start..mid].to_vec();
                let mut right = arr[mid..end].to_vec();
                merge(&mut left, &mut right, &mut arr[start..end]);
            }
        }
        size *= 2;
    }
}

fn main() {
    let mut numbers = vec![5, 21, 7, 23, 19, 1, 6, 3, 12, 17, 10];
    println!("Before sorting: {:?}", numbers);
    timsort(&mut numbers);
    println!("After sorting: {:?}", numbers);
}

Output:

Before sorting: [5, 21, 7, 23, 19, 1, 6, 3, 12, 17, 10]
After sorting: [1, 3, 5, 6, 7, 10, 12, 17, 19, 21, 23]

Explanation of the Code

1. Insertion Sort: This is used for sorting small runs (subarrays). It’s efficient for small datasets and is used within TimSort to sort runs smaller than the MinRun size.
2. Merge Function: This function merges two sorted arrays (runs) into a single sorted array, just like in Merge Sort. TimSort uses this to merge the sorted runs.
3. MinRun Calculation: TimSort dynamically calculates the minimum size of runs based on the array’s length. Smaller arrays are handled with fewer passes of Merge Sort.
4. TimSort Implementation:
   • First, TimSort sorts small sections of the array using Insertion Sort.
   • Then, it merges these sorted sections (runs) like Merge Sort. This ensures the overall time complexity is O(n log n), even in the worst case.

Rust-Specific Details

1. Ord Trait:
   • In Rust, the Ord trait is used to define types that can be ordered. Since we are comparing elements in the array, the type T must implement the Ord trait. This allows us to use operators like <, >, <=, and >= to compare elements during sorting.
   • In the function signature, we specify T: Ord to ensure the elements can be ordered.
2. Clone Trait:
   • Rust enforces memory safety with its ownership model. Since we are working with elements in an array and might need to move or shift elements around, the elements need to be cloned rather than moved.
   • The Clone trait is used to duplicate values explicitly. We use clone() to create a copy of the element while keeping the original in place. For types that are not Copy (e.g., larger structs or vectors), we must use Clone to avoid violating Rust’s ownership rules.
   • The function signature uses T: Ord + Clone to ensure that the type T can be both compared and cloned.
3. In-Place Sorting:
   • Insertion Sort in Rust is an in-place sorting algorithm, meaning it does not require additional memory allocation outside of the input array. We use mutable references (&mut) to modify the array directly.
   • This makes the algorithm space-efficient with a space complexity of O(1), as no extra memory is allocated during the sorting process.

Step-by-Step Explanation of TimSort with Example

We’ll walk through how TimSort processes this array. For this example, assume the minimum run size (min_run) is 4.

1. Identifying Runs

TimSort starts by identifying “runs,” which are consecutive sections of the array that are already sorted. TimSort will extend a run and sort it using Insertion Sort if it is too short.

• Initial array: [5, 21, 7, 23, 19, 1, 6, 3, 12, 17, 10]

Let’s divide this array into runs:

• Run 1: From index 0 to 3: [5, 21, 7, 23]
  • This is not sorted, so we sort it using Insertion Sort.
• Run 2: From index 4 to 7: [19, 1, 6, 3]
  • This is a descending run, so TimSort will reverse it into an ascending order before sorting with Insertion Sort.
• Run 3: From index 8 to 10: [12, 17, 10]
  • This is not sorted, so it will also be sorted using Insertion Sort.

---

2. Sorting Runs with Insertion Sort

Let’s sort the runs.

• Run 1 (Sorting [5, 21, 7, 23] using Insertion Sort):
  1. Initial run: [5, 21, 7, 23]
  2. Compare 21 > 5 → No change.
  3. Compare 7 < 21 → Shift 21 to the right. Array becomes [5, 21, 21, 23]. Insert 7. Result: [5, 7, 21, 23].
  4. Compare 23 > 21 → No change.
  • Result after sorting Run 1: [5, 7, 21, 23]
• Run 2 (Sorting [19, 1, 6, 3] using Insertion Sort):
  1. Initial run (after reversing): [3, 6, 1, 19]
  2. Compare 6 > 3 → No change.
  3. Compare 1 < 6 → Shift 6 to the right. Array becomes [3, 6, 6, 19]. Then shift 3 to the right. Array becomes [3, 3, 6, 19]. Insert 1. Result: [1, 3, 6, 19].
  4. Compare 19 > 6 → No change.
  • Result after sorting Run 2: [1, 3, 6, 19]
• Run 3 (Sorting [12, 17, 10] using Insertion Sort):
  1. Initial run: [12, 17, 10]
  2. Compare 17 > 12 → No change.
  3. Compare 10 < 17 → Shift 17 to the right. Array becomes [12, 17, 17]. Insert 10. Result: [10, 12, 17].
  • Result after sorting Run 3: [10, 12, 17]

---

3. Merging Runs

After sorting the runs, TimSort merges them using a process similar to Merge Sort. Let’s go through the merges step-by-step.

• Merge Run 1 and Run 2:
  • Merging [5, 7, 21, 23] and [1, 3, 6, 19].
  • Compare 1 < 5 → Place 1.
  • Compare 3 < 5 → Place 3.
  • Compare 5 < 6 → Place 5.
  • Compare 6 < 7 → Place 6.
  • Compare 7 < 19 → Place 7.
  • Compare 19 < 21 → Place 19.
  • Place the remaining elements [21, 23].
  • Result after merging Run 1 and Run 2: [1, 3, 5, 6, 7, 19, 21, 23]
• Merge the result with Run 3:
  • Merging [1, 3, 5, 6, 7, 19, 21, 23] and [10, 12, 17].
  • Compare 1 < 10 → Place 1.
  • Compare 3 < 10 → Place 3.
  • Compare 5 < 10 → Place 5.
  • Compare 6 < 10 → Place 6.
  • Compare 7 < 10 → Place 7.
  • Compare 10 < 19 → Place 10.
  • Compare 12 < 19 → Place 12.
  • Compare 17 < 19 → Place 17.
  • Place the remaining elements [19, 21, 23].
  • Final sorted array: [1, 3, 5, 6, 7, 10, 12, 17, 19, 21, 23]

One point to note is that TimSort’s exact behaviour can vary slightly depending on the implementation and the specific parameters used (like the minimum run size). The process we have described is a simplified version that captures the essence of TimSort’s operation.

In a full TimSort implementation, there would be additional optimizations and checks, such as:

• Galloping mode during merging to handle cases where one run has many elements smaller than the other.
• Balancing the lengths of merged runs to maintain good performance.
• Using temporary storage for merging to improve efficiency.

Performance Test: Timsort vs Quick Sort vs Merge Sort

Now that we’ve implemented TimSort, let’s evaluate its performance by comparing it to two other popular sorting algorithms: Quick Sort and Merge Sort. We will include both the original Quick Sort algorithm and the optimized median-of-three Quick Sort algorithm. We use the median-of-three variant because it helps mitigate Quick Sort’s worst-case performance on already sorted or reverse-sorted arrays by choosing a more reliable pivot. We will test the algorithms on random, sorted, and reverse-sorted arrays of varying sizes (1000, 5000, and 10,000 elements).

Benchmarking Setup

We’ll use Rust’s std::time::Instant for benchmarking and for generating arrays, we can utilize the rand crate to create random arrays and manual loops to generate sorted and reverse-sorted arrays.

When performing your tests, include rand in the under the [dependencies] section of your Cargo.toml file, for example:

[package]
name = "insertion_sort"
version = "0.1.0"
edition = "2021"

[dependencies]
rand = "0.9.0-alpha.2"

Below is the Rust benchmarking code, which compares Timsort, Quick Sort (original and median-of-three optimized), and Merge Sort. We won’t include TimSort again, as the implementation is shown above.

Merge Sort Implementation in Rust

fn merge_sort<T: Ord + Clone>(arr: &mut [T]) {
    if arr.len() > 1 {
        let mid = arr.len() / 2;
        let mut left = arr[..mid].to_vec();
        let mut right = arr[mid..].to_vec();

        merge_sort(&mut left);
        merge_sort(&mut right);

        merge(&mut left, &mut right, arr);
    }
}

Original Quick Sort Implementation in Rust

fn quick_sort<T: Ord>(arr: &mut [T]) {
    quick_sort_recursive(arr, 0, arr.len());
}

fn quick_sort_recursive<T: Ord>(arr: &mut [T], low: usize, high: usize) {
    if high - low <= 1 {
        return;
    }

    let pivot = partition(arr, low, high);
    quick_sort_recursive(arr, low, pivot);
    quick_sort_recursive(arr, pivot + 1, high);
}

fn partition<T: Ord>(arr: &mut [T], low: usize, high: usize) -> usize {
    let pivot = high - 1;
    let mut i = low;
    for j in low..pivot {
        if arr[j] < arr[pivot] {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, pivot);
    i
}

Median-of-Three Optimized Quick Sort Implementation in Rust

fn median_of_three<T: Ord>(arr: &mut [T], low: usize, mid: usize, high: usize) {
    if arr[low] > arr[mid] {
        arr.swap(low, mid);
    }
    if arr[low] > arr[high] {
        arr.swap(low, high);
    }
    if arr[mid] > arr[high] {
        arr.swap(mid, high);
    }
    arr.swap(mid, high - 1);
}

fn quick_sort_median_three<T: Ord + Clone>(arr: &mut [T]) {
    quick_sort_median_three_recursive(arr, 0, arr.len());
}

fn quick_sort_median_three_recursive<T: Ord + Clone>(arr: &mut [T], low: usize, high: usize) {
    if high - low <= 1 {
        return;
    }

    if high - low <= 3 {
        insertion_sort(&mut arr[low..high]); // Fallback to insertion sort for small arrays
        return;
    }

    let mid = (low + high) / 2;
    median_of_three(arr, low, mid, high - 1);

    let pivot = partition(arr, low, high - 1);
    quick_sort_median_three_recursive(arr, low, pivot);
    quick_sort_median_three_recursive(arr, pivot + 1, high);
}

Benchmarking Code

use rand::seq::SliceRandom;
use std::time::Instant;

// Benchmarking Function
fn benchmark(sort_fn: fn(&mut [i32]), arr: &mut [i32], name: &str) {
    let start = Instant::now();
    sort_fn(arr);
    let duration = start.elapsed();
    println!("{}: {:?}", name, duration);
}

fn main() {
    let mut rng = rand::thread_rng();
    let sizes = [1000, 5000, 10000];

    for &size in &sizes {
        println!("\nArray size: {}", size);

        // Random array
        let mut arr: Vec<i32> = (0..size).collect();
        arr.shuffle(&mut rng);
        benchmark(timsort, &mut arr.clone(), "TimSort (random)");
        benchmark(merge_sort, &mut arr.clone(), "Merge Sort (random)");
        benchmark(quick_sort, &mut arr.clone(), "Original Quick Sort (random)");
        benchmark(quick_sort_median_three, &mut arr.clone(), "Quick Sort with Median-of-Three (random)");

        // Sorted array
        arr.sort();
        benchmark(timsort, &mut arr.clone(), "TimSort (sorted)");
        benchmark(merge_sort, &mut arr.clone(), "Merge Sort (sorted)");
        benchmark(quick_sort, &mut arr.clone(), "Original Quick Sort (sorted)");
        benchmark(quick_sort_median_three, &mut arr.clone(), "Quick Sort with Median-of-Three (sorted)");

        // Reverse sorted array
        arr.reverse();
        benchmark(timsort, &mut arr.clone(), "TimSort (reverse)");
        benchmark(merge_sort, &mut arr.clone(), "Merge Sort (reverse)");
        benchmark(quick_sort, &mut arr.clone(), "Original Quick Sort (reverse)");
        benchmark(quick_sort_median_three, &mut arr.clone(), "Quick Sort with Median-of-Three (reverse)");
    }
}

Results

TimSort vs Merge Sort vs Quick Sort (Original and Median-of-Three)

Array Size & Configuration	TimSort	Merge Sort	Original Quick Sort	Quick Sort (Median-of-Three)
1000 (Random)	0.358	0.826	0.551	0.548
1000 (Sorted)	0.107	0.742	35.092	0.304
1000 (Reverse)	0.276	0.715	17.872	0.411
5000 (Random)	0.863	2.339	3.087	3.326
5000 (Sorted)	0.341	2.845	683.574	1.641
5000 (Reverse)	1.036	1.949	370.185	2.374
10000 (Random)	1.971	4.767	5.281	5.041
10000 (Sorted)	0.730	4.323	2405.938	4.342
10000 (Reverse)	2.536	5.275	1529.952	6.150

Note: Times are rounded to one decimal place for readability. Actual performance may vary slightly due to system-specific factors.

The text is generally well-written and grammatically correct. However, I can suggest a few minor improvements to enhance its flow and clarity. Here’s a revised version:

Analysis of Results

TimSort

• TimSort consistently performed well across all scenarios, particularly on sorted and reverse-sorted data, where it was the fastest algorithm. This is due to its hybrid nature, utilizing Insertion Sort for small runs and Merge Sort for larger segments. It leverages the pre-existing order (runs) in the data, giving it an advantage in sorted and nearly sorted datasets.
• TimSort’s performance remained close to Merge Sort and Quick Sort on random data, but it clearly outperformed the Original Quick Sort in cases where the data was sorted or reverse-sorted.

Merge Sort

• Merge Sort provided stable and consistent performance across all data configurations. It was slower than TimSort in most scenarios, particularly on sorted and reverse-sorted data, because it doesn’t take advantage of pre-existing order as TimSort does.
• Merge Sort was still slower than both Quick Sort variants on random data but competitive with TimSort.

Original Quick Sort

• Original Quick Sort struggled significantly with sorted and reverse-sorted arrays, degrading to O(n²) time complexity. The performance in these cases was much worse compared to other algorithms. For instance, on a sorted array of size 10,000, it took 2.4 seconds, making it the slowest of the tested algorithms.
• On random data, Original Quick Sort performed reasonably well, close to TimSort and Merge Sort but still slower than the Median-of-Three Quick Sort.

Quick Sort with Median-of-Three

• The Median-of-Three Quick Sort consistently outperformed the Original Quick Sort, particularly on sorted and reverse-sorted arrays. It mitigated the worst-case performance issue that Quick Sort encounters on such arrays by selecting a better pivot, significantly improving speed.
• In almost every scenario, the Median-of-Three Quick Sort was faster than Merge Sort and very close to TimSort on random data.

Key Takeaways

• TimSort is the clear winner when the array is sorted or nearly sorted. It outperforms other algorithms because it can take advantage of the existing order within the data.
• Merge Sort provides predictable O(n log n) performance but does not handle pre-sorted data as efficiently as TimSort.
• Original Quick Sort performs poorly on sorted or reverse-sorted data, confirming its O(n²) worst-case behaviour.
• Median-of-Three Optimized Quick Sort avoids the pitfalls of the original Quick Sort and improves performance across the board, making it more competitive, especially on reverse-sorted data. However, it still doesn’t match TimSort’s efficiency on sorted data.

Pros and Cons of Using TimSort

Pros:

1. Efficient for Real-World Data: TimSort is particularly fast for datasets that contain ordered or nearly ordered sequences, making it suitable for real-world applications.
2. Stable Sort: TimSort preserves the relative order of elements with equal values, making it a stable sorting algorithm.
3. Adaptive to Input: TimSort is adaptive, meaning it performs better on data that is already partially sorted.

Cons:

1. Slightly More Complex: TimSort is more complex to implement than basic algorithms like Quick Sort or Insertion Sort.
2. Space Overhead: TimSort uses additional space for the merging process, which may not be ideal in memory-constrained environments.

When to Use TimSort

TimSort is an ideal sorting algorithm when:

1. You have partially sorted or nearly sorted data: Since TimSort is designed to handle ordered sequences efficiently, it’s perfect for real-world data that often has some ordering.
2. You need a stable sorting algorithm: TimSort ensures that the relative order of elements is preserved, making it suitable for datasets where stability matters.
3. You need an adaptive sorting algorithm: TimSort adapts to the existing order in the data, making it faster in practice than other O(n log n) algorithms.

Conclusion

TimSort is a highly efficient and adaptive sorting algorithm that excels at handling real-world datasets with pre-existing order. Its hybrid nature, combining Insertion Sort for small runs and Merge Sort for larger segments, allows it to perform exceptionally well on sorted and nearly sorted data. This adaptability gives TimSort a significant edge in cases where other algorithms, like Merge Sort or Quick Sort, may struggle.

Whether you’re dealing with small, sorted, or reverse-sorted arrays, TimSort’s efficiency, stability, and adaptability make it an essential tool for developers. It combines the best of Insertion Sort and Merge Sort to handle diverse datasets and is a reliable go-to algorithm for many practical applications.

Congratulations on reading to the end of the tutorial!

In Python – How to do TimSort in Python

In C++ – How to Do TimSort in C++

In JavaScript – How to do TimSort in JavaScript

In Java – How to do TimSort in Java

Have fun and happy researching!