How To Do Quick Sort in Rust

Introduction

Tony Hoare introduced Quick Sort in 1960. It remains one of the most efficient and widely used sorting algorithms. Known for its average-case time complexity of O(n log n) and in-place sorting capabilities, Quick Sort is a go-to choice for sorting large datasets. In this blog post, we’ll explore how to implement Quick Sort in Rust, walking through both the original implementation and the more advanced “median-of-three” pivot selection technique.

What is Quick Sort

Quick Sort is one of the fastest sorting algorithms in practice, with an average time complexity of O(n log n). It works by selecting a “pivot” element, partitioning the array into two subarrays, and recursively sorting those subarrays.

The choice of pivot plays a critical role in the efficiency of Quick Sort. An unbalanced partition can lead to worst-case time complexity O(n²). That’s why alternative methods, such as the “median-of-three” pivot strategy, improve performance in cases where the input is already sorted or reverse sorted.

Below, you can see a visualization of how Quick Sort works. Choose the length of your array in the box next to Array Size (Max 30) then click Generate Random Array to generate the numbers, then click Start Sorting.

Pseudocode for Quick Sort

Here’s the basic pseudocode for Quick Sort:

procedure quickSort(arr, low, high)
    if low < high then
        pivotIndex = partition(arr, low, high)   // Step 1: Partition the array
        quickSort(arr, low, pivotIndex - 1)      // Step 2: Recursively sort the left sub-array
        quickSort(arr, pivotIndex + 1, high)     // Step 3: Recursively sort the right sub-array

procedure partition(arr, low, high)
    pivot = arr[high]        // Step 4: Choose the pivot (last element in the array)
    i = low - 1              // Step 5: Initialize i to point to the element before the sub-array

    for j = low to high - 1  // Step 6: Iterate over the array from low to high - 1
        if arr[j] <= pivot then
            i = i + 1          // Step 7: Increment i
            swap arr[i] with arr[j]  // Step 8: Swap arr[i] and arr[j] (elements less than the pivot)

    swap arr[i + 1] with arr[high]  // Step 9: Place the pivot in its correct position
    return i + 1                   // Step 10: Return the pivot index

Step-by-Step Breakdown of the Pseudocode

Quick Sort Function (Main Recursive Function)

1. Base Condition:
   • The function checks if low is less than high. If not, it means the array or sub-array has only one or zero elements already sorted, so we stop.
   • This condition ensures the recursive function terminates when the sub-array size becomes 1 or 0.
2. Partition the Array:
   • The partition() function is called to rearrange the elements in the array so that all elements smaller than the pivot are on the left and all elements larger are on the right. The pivot is placed in its correct position in the sorted array.
   • After the partitioning step, the array is divided into two sections: the left and right of the pivot.
3. Recursively Sort the Left and Right Sub-arrays:
   • The quickSort() function is called recursively on the left sub-array (low to pivotIndex - 1), which contains elements smaller than the pivot.
   • It is also called on the right sub-array (pivotIndex + 1 to high), which contains elements larger than the pivot.
   • This process continues until all sub-arrays are fully sorted.

Partition Function (Rearranges the Array Around the Pivot)

4. Select the Pivot:
   • The pivot is usually selected as the last element (arr[high]). The goal is to place this pivot in its correct sorted position.
5. Initialize the Index for Smaller Elements (i):
   • Set i to low - 1, which points to the position before the first element of the sub-array. This is important because i will track the “boundary” between elements smaller than the pivot and those larger than the pivot.
6. Iterate Over the Array (j Loop):
   • A loop runs from low to high - 1 (excluding the pivot itself).
   • We compare each element in this loop to the pivot.
7. Check If the Current Element is Smaller or Equal to the Pivot:
   • If the element at arr[j] is smaller than or equal to the pivot, it means it should be on the left side of the pivot.
   • We increment i to include the current element in the “smaller elements” section.
8. Swap Elements to Place Smaller Elements on the Left:
   • Swap arr[i] with arr[j]. This ensures that all elements less than or equal to the pivot end up on the left side of the pivot.
9. Place the Pivot in the Correct Position:
   • After the loop ends, swap arr[i + 1] with the pivot (arr[high]). This places the pivot in its correct position in the sorted array, as all elements to its left are smaller, and all elements to its right are larger.
10. Return the Pivot Index:

• Finally, return i + 1 as the new pivot index. This index will further divide the array into sub-arrays for recursive sorting.

Rust Quick Sort Implementation

Here’s a straightforward implementation of Quick Sort in Rust using the last element as the pivot:

fn quick_sort(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }
    
    let pivot_index = partition(arr);
    quick_sort(&mut arr[0..pivot_index]);
    quick_sort(&mut arr[pivot_index + 1..]);
}

fn partition(arr: &mut [i32]) -> usize {
    let len = arr.len();
    let pivot = arr[len - 1];  // Choose the last element as the pivot
    let mut i = 0;

    for j in 0..len - 1 {
        if arr[j] <= pivot {
            arr.swap(i, j);
            i += 1;
        }
    }
    
    arr.swap(i, len - 1);  // Place the pivot in its correct position
    i
}

fn main() {
    let mut arr = [34, 7, 23, 32, 5, 62];
    quick_sort(&mut arr);
    println!("{:?}", arr);
}

Output:

[5, 7, 23, 32, 34, 62]

Step-by-Step Explanation of Example

Let’s walk through how the original Quick Sort (with the last element as the pivot) works on the array [34, 7, 23, 32, 5, 62].

Initial Array:

• Input: [34, 7, 23, 32, 5, 62]

Step 1: Choosing the Pivot

• The last element, 62, is chosen as the pivot.
• We now partition the array around this pivot.

Step 2: Partitioning

• We iterate over the array from the first element to the second-to-last element (excluding the pivot) and compare each element with the pivot (62).
• Initially, the index i (for smaller elements) is set to 0.

1. Compare 34 with 62. Since 34 <= 62, we swap arr[i] with arr[0] (which is 34 itself). Then, we increment i to 1.
2. Compare 7 with 62. Since 7 <= 62, we swap arr[i] with arr[1] (which is 7 itself). Then, increment i to 2.
3. Compare 23 with 62. Since 23 <= 62, we swap arr[i] with arr[2] (which is 23 itself). Then, increment i to 3.
4. Compare 32 with 62. Since 32 <= 62, we swap arr[i] with arr[3] (which is 32 itself). Then, increment i to 4.
5. Compare 5 with 62. Since 5 <= 62, we swap arr[i] with arr[4] (which is 5 itself). Then, increment i to 5.

After all comparisons, the index i = 5.

Step 3: Placing the Pivot

• Now, we place the pivot (62) in its correct position. Since i = 5, we swap arr[5] (which is 62) with itself. The array remains the same.
• Result after partitioning: [34, 7, 23, 32, 5, 62].

Step 4: Recursive Sorting (Left Subarray)

• The array is now split into two parts: [34, 7, 23, 32, 5] (left) and [62] (right).
• The right part [62] is already sorted.
• We apply Quick Sort recursively to the left part [34, 7, 23, 32, 5].

Step 5: Choosing the Pivot (Left Subarray)

• The last element, 5, is chosen as the pivot for the left subarray.
• We now partition this subarray around the pivot (5).

Step 6: Partitioning (Left Subarray)

• We iterate over the subarray [34, 7, 23, 32] and compare each element with 5.
• Initially, i = 0.

1. Compare 34 with 5. Since 34 > 5, no swap is made.
2. Compare 7 with 5. Since 7 > 5, no swap is made.
3. Compare 23 with 5. Since 23 > 5, no swap is made.
4. Compare 32 with 5. Since 32 > 5, no swap is made.

After all comparisons, i remains 0.

Step 7: Placing the Pivot (Left Subarray)

• Now, we place the pivot 5 in its correct position by swapping it with arr[0]. The array becomes [5, 7, 23, 32, 34, 62].

Step 8: Recursive Sorting (Left and Right Subarrays)

• The array is now split into two parts: [5] (left), [7, 23, 32, 34] (middle), and [62] (right).
• The left part [5] and the right part [62] are already sorted.
• We apply Quick Sort recursively to the middle part [7, 23, 32, 34].

Step 9: Choosing the Pivot (Middle Subarray)

• The last element, 34, is chosen as the pivot for the middle subarray.
• We now partition this subarray around the pivot (34).

Step 10: Partitioning (Middle Subarray)

• We iterate over [7, 23, 32] and compare each element with 34.
• Initially, i = 0.

1. Compare 7 with 34. Since 7 <= 34, we swap arr[i] with arr[0] (which is 7 itself). Then, increment i to 1.
2. Compare 23 with 34. Since 23 <= 34, we swap arr[i] with arr[1] (which is 23 itself). Then, increment i to 2.
3. Compare 32 with 34. Since 32 <= 34, we swap arr[i] with arr[2] (which is 32 itself). Then, increment i to 3.

Step 11: Placing the Pivot (Middle Subarray)

• Now, we place the pivot 34 in its correct position by swapping it with arr[3] (which is 34 itself).
• The array remains [5, 7, 23, 32, 34, 62].

Step 12: Recursive Sorting (Final)

• The array is now split into [7, 23, 32] (left) and [34] (right).
• The right part [34] is already sorted.
• Apply Quick Sort recursively to the left part [7, 23, 32].

Step 13: Sorting the Final Left Subarray

• Choose the last element 32 as the pivot for [7, 23, 32].
• Partition the subarray: Compare 7 and 23 with 32. Both are less than or equal to 32, so no swaps are needed.
• Place the pivot 32 in its correct position.

Step 14: Final Sorted Array

• After recursively sorting all subarrays, we get the fully sorted array:
  • [5, 7, 23, 32, 34, 62].

Optimized Quicksort with Median-of-Three

Now, let’s implement an optimized version of Quick Sort using the median-of-three method for pivot selection.

Median-of-Three Pivot Selection

The median-of-three method selects the pivot as the median of the array’s first, middle, and last elements. This approach avoids the worst-case scenario of choosing a poor pivot (like the smallest or largest element) and provides better performance for partially sorted arrays.

Let’s implement the median-of-three function:

// Function to choose the median of the first, middle, and last element as the pivot
fn median_of_three(arr: &mut [i32]) -> usize {
    let len = arr.len();
    let first = 0;         // Index of the first element
    let middle = len / 2;  // Index of the middle element
    let last = len - 1;    // Index of the last element
    
    // Ensure that the first element is smaller than the middle element
    if arr[first] > arr[middle] {
        arr.swap(first, middle);
    }
    // Ensure that the first element is smaller than the last element
    if arr[first] > arr[last] {
        arr.swap(first, last);
    }
    // Ensure that the middle element is smaller than the last element
    if arr[middle] > arr[last] {
        arr.swap(middle, last);
    }
    
    middle // Return the index of the median (which is the middle one now)
}

// Recursive Quick Sort function that uses the median-of-three pivot selection
fn quick_sort_median_of_three(arr: &mut [i32]) {
    // Base case: If the array has one or no elements, it's already sorted
    if arr.len() <= 1 {
        return;
    }
    
    // Partition the array and get the pivot index
    let pivot_index = partition_median_of_three(arr);
    
    // Recursively sort the elements before and after the pivot
    quick_sort_median_of_three(&mut arr[0..pivot_index]);     // Left subarray
    quick_sort_median_of_three(&mut arr[pivot_index + 1..]);  // Right subarray
}

// Partition the array around the median-of-three pivot
fn partition_median_of_three(arr: &mut [i32]) -> usize {
    // Find the median-of-three pivot and move it to the front
    let pivot_index = median_of_three(arr);
    arr.swap(0, pivot_index); // Move the median element to the front of the array
    
    let pivot = arr[0];       // Choose the pivot as the first element
    let mut low = 1;          // Low pointer starts at the second element
    let mut high = arr.len() - 1;  // High pointer starts at the last element

    loop {
        // Move the high pointer left until we find an element smaller than the pivot
        while low <= high && arr[high] >= pivot {
            high -= 1;
        }
        // Move the low pointer right until we find an element greater than the pivot
        while low <= high && arr[low] <= pivot {
            low += 1;
        }
        // Swap elements at the low and high pointers if they are out of order
        if low <= high {
            arr.swap(low, high);
        } else {
            break;  // Exit the loop when low and high pointers cross
        }
    }
    
    // Place the pivot element in its correct position
    arr.swap(0, high);
    
    high // Return the final pivot index
}

fn main() {
    // Example usage of the Quick Sort with median-of-three pivot selection
    let mut arr = [34, 7, 23, 32, 5, 62];
    
    // Sort the array using Quick Sort with the median-of-three pivot strategy
    quick_sort_median_of_three(&mut arr);
    
    // Print the sorted array
    println!("{:?}", arr);
}

Output:

[5, 7, 23, 32, 34, 62]

Step-by-Step Explanation of Example

Let’s go step-by-step through how the median-of-three Quick Sort works on the array [34, 7, 23, 32, 5, 62].

Initial Array:

• Input: [34, 7, 23, 32, 5, 62]

Step 1: Choosing the Median of Three

• The first element is 34.
• The middle element (at index 2) is 23.
• The last element is 62.

Now, we compare these three elements:

1. Compare 34 and 23: Since 34 > 23, we swap them. The array becomes [23, 7, 34, 32, 5, 62].
2. Compare 23 and 62: Since 23 < 62, no swap is needed.
3. Compare 34 and 62: Since 34 < 62, no swap is needed.

After applying the median-of-three logic, the median value (34) is already at its middle position (index 2).

Step 2: Placing the Pivot

• The median-of-three pivot is now chosen as 34 (middle element).
• We swap the median value (34) with the first element. The array becomes [34, 7, 23, 32, 5, 62].

Step 3: Partitioning

• Now, we start partitioning the array with 34 as the pivot.
• We initialize two pointers:
  • low = 1 (pointing to the second element).
  • high = 5 (pointing to the last element).

We begin comparing and swapping elements based on the pivot 34:

1. Compare 62 and 34: Since 62 > 34, decrement high to 4.
2. Compare 5 and 34: Since 5 < 34, increment low to 2.
3. Compare 23 and 34: Since 23 < 34, increment low to 3.
4. Compare 32 and 34: Since 32 < 34, increment low to 4.

Now, the low pointer has crossed high, so we stop the loop and swap the pivot 34 with the element at high (32). The array becomes:

• [32, 7, 23, 5, 34, 62]

At this point, the pivot 34 is correctly placed in its final sorted position (index 4).

Step 4: Recursive Sorting (Left Subarray)

• The array is now split into two parts: [32, 7, 23, 5] (left) and [62] (right).
• The right part [62] is already sorted.
• We apply Quick Sort recursively to the left part [32, 7, 23, 5].

Step 5: Choosing the Median of Three (Left Subarray)

• The first element is 32.
• The middle element (at index 1) is 7.
• The last element is 5.

Now, we compare these three elements:

1. Compare 32 and 7: Since 32 > 7, we swap them. The array becomes [7, 32, 23, 5].
2. Compare 7 and 5: Since 7 > 5, we swap them. The array becomes [5, 32, 23, 7].
3. Compare 32 and 7: Since 32 > 7, we swap them. The array becomes [5, 7, 23, 32].

After applying the median-of-three logic, the median value (7) is now the first element.

Step 6: Placing the Pivot (Left Subarray)

• The pivot is chosen as 7 (now at index 0).
• We partition the array with 7 as the pivot.

Step 7: Partitioning (Left Subarray)

• The pivot 7 is at the first position. We initialize low = 1 and high = 3:

1. Compare 32 and 7: Since 32 > 7, decrement high to 2.
2. Compare 23 and 7: Since 23 > 7, decrement high to 1.

Now, the low pointer has crossed high, so we stop the loop and swap the pivot 7 with itself (since it’s already in the correct position).

The left subarray after partitioning becomes:

• [5, 7, 23, 32].

Step 8: Recursive Sorting (Left and Right Subarrays)

• The array is now split into [5] (left) and [23, 32] (right).
• The left part [5] is already sorted.
• We apply Quick Sort recursively to the right part [23, 32].

Step 9: Sorting the Final Right Subarray

• Choose the median of three for [23, 32]:
  • The first element is 23.
  • The middle element (index 0) is 23.
  • The last element is 32.

The median value is 23, which is already in its correct position. The subarray [23, 32] is already sorted.

Step 10: Final Sorted Array

• After recursively sorting all subarrays, we get the fully sorted array:
  • [5, 7, 23, 32, 34, 62].

Time Complexity

The time complexity of Quick Sort depends on how balanced the partitioning is at each step:

• Best Case:
  The best-case scenario occurs when the pivot divides the array into two equal parts at each recursive step. In this case, the time complexity is:
  • O(n log n)
• Average Case:
  On average, Quick Sort performs well due to the random nature of the pivot selection, leading to a nearly balanced partition. Thus, the average time complexity is:
  • O(n log n)
• Worst Case:
  The worst-case scenario occurs when the pivot is always the smallest or largest element, leading to highly unbalanced partitions. This happens when the input array is sorted (ascending or descending), and the first or last element is chosen as the pivot (e.g., in the original implementation). In this case, the time complexity becomes:
  • O(n²)

The median-of-three approach helps mitigate this problem by reducing the likelihood of selecting a poor pivot, thereby preventing the worst-case time complexity in most practical scenarios.

Space Complexity

• Original Quick Sort:
  Quick Sort is an in-place sorting algorithm, which means it doesn’t require additional storage for the input array except for the recursive function calls.
  • Space Complexity (Original): O(log n) for the recursion stack.
• Median-of-Three Quick Sort:
  The median-of-three strategy does not significantly alter the space complexity because it only involves constant element comparisons (O(1)) to determine the median. The recursion depth still contributes to the space complexity.
  • Space Complexity (Median-of-Three): O(log n)

Performance Test Comparing Original and Median-Of-Three Quick Sort

For this performance test, we will measure the sorting time for arrays of three types (random, sorted, and reverse sorted) with lengths 1000, 10,000, and 100,000.

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"

Test Setup

We’ll test three different array types:

1. Random Array: An array filled with random integers.
2. Sorted Array: An array in ascending order.
3. Reverse Sorted Array: An array in descending order.

The test will be repeated for array sizes of 1000, 10,000, and 50,000.

Here’s the code setup for the performance comparison:

use std::time::Instant;
use rand::Rng;

fn quick_sort(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }
    let pivot_index = partition(arr);
    quick_sort(&mut arr[0..pivot_index]);
    quick_sort(&mut arr[pivot_index + 1..]);
}

fn partition(arr: &mut [i32]) -> usize {
    let len = arr.len();
    let pivot = arr[len - 1];
    let mut i = 0;

    for j in 0..len - 1 {
        if arr[j] <= pivot {
            arr.swap(i, j);
            i += 1;
        }
    }

    arr.swap(i, len - 1);
    i
}

fn quick_sort_median_of_three(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }
    let pivot_index = partition_median_of_three(arr);
    quick_sort_median_of_three(&mut arr[0..pivot_index]);
    quick_sort_median_of_three(&mut arr[pivot_index + 1..]);
}

fn partition_median_of_three(arr: &mut [i32]) -> usize {
    let pivot_index = median_of_three(arr);
    arr.swap(0, pivot_index);

    let pivot = arr[0];
    let mut low = 1;
    let mut high = arr.len() - 1;

    loop {
        while low <= high && arr[high] >= pivot {
            high -= 1;
        }
        while low <= high && arr[low] <= pivot {
            low += 1;
        }
        if low <= high {
            arr.swap(low, high);
        } else {
            break;
        }
    }

    arr.swap(0, high);
    high
}

fn median_of_three(arr: &mut [i32]) -> usize {
    let len = arr.len();
    let first = 0;
    let middle = len / 2;
    let last = len - 1;

    if arr[first] > arr[middle] {
        arr.swap(first, middle);
    }
    if arr[first] > arr[last] {
        arr.swap(first, last);
    }
    if arr[middle] > arr[last] {
        arr.swap(middle, last);
    }

    middle
}

fn generate_random_array(size: usize) -> Vec<i32> {
    let mut rng = rand::thread_rng();
    (0..size).map(|_| rng.gen_range(0..100000)).collect()
}

fn generate_sorted_array(size: usize) -> Vec<i32> {
    (0..size as i32).collect()
}

fn generate_reverse_sorted_array(size: usize) -> Vec<i32> {
    (0..size as i32).rev().collect()
}

fn measure_time<F>(mut arr: Vec<i32>, sort_fn: F) -> f64
where
    F: Fn(&mut [i32]),
{
    let start = Instant::now();
    sort_fn(&mut arr);
    let duration = start.elapsed();
    duration.as_secs_f64()
}

fn main() {
    let sizes = [1000, 10_000, 50_000];

    for &size in sizes.iter() {
        let random_array = generate_random_array(size);
        let sorted_array = generate_sorted_array(size);
        let reverse_sorted_array = generate_reverse_sorted_array(size);

        // Testing Original Quick Sort
        println!("\nArray Size: {}", size);

        println!("Original Quick Sort - Random Array:");
        let time_random = measure_time(random_array.clone(), quick_sort);
        println!("Time: {:.6} seconds", time_random);

        println!("Original Quick Sort - Sorted Array:");
        let time_sorted = measure_time(sorted_array.clone(), quick_sort);
        println!("Time: {:.6} seconds", time_sorted);

        println!("Original Quick Sort - Reverse Sorted Array:");
        let time_reverse_sorted = measure_time(reverse_sorted_array.clone(), quick_sort);
        println!("Time: {:.6} seconds", time_reverse_sorted);

        // Testing Median of Three Quick Sort
        println!("\nMedian of Three Quick Sort - Random Array:");
        let time_random_median = measure_time(random_array.clone(), quick_sort_median_of_three);
        println!("Time: {:.6} seconds", time_random_median);

        println!("Median of Three Quick Sort - Sorted Array:");
        let time_sorted_median = measure_time(sorted_array.clone(), quick_sort_median_of_three);
        println!("Time: {:.6} seconds", time_sorted_median);

        println!("Median of Three Quick Sort - Reverse Sorted Array:");
        let time_reverse_sorted_median = measure_time(reverse_sorted_array.clone(), quick_sort_median_of_three);
        println!("Time: {:.6} seconds", time_reverse_sorted_median);
    }
}

Output:

Array Size	Array Type	Original Quick Sort (seconds)	Median-of-Three Quick Sort (seconds)
1000	Random	0.000635	0.000295
	Sorted	0.044917	0.000140
	Reverse Sorted	0.023478	0.000127
10000	Random	0.008797	0.013265
	Sorted	2.635353	0.001940
	Reverse Sorted	1.805723	0.001905
50000	Random	0.041102	0.020111
	Sorted	84.106747	0.006669
	Reverse Sorted	37.301224	0.007791

Key Takeaways

Performance on Random Arrays

For smaller arrays (size 1000), the original Quick Sort slightly outperforms the median-of-three due to its simpler pivot selection process, which reduces overhead. However, as array size grows, the median-of-three Quick Sort becomes more efficient because its pivot selection reduces the likelihood of unbalanced partitions, which is crucial for larger arrays (size 50000).

Performance on Sorted and Reverse Sorted Arrays

The original Quick Sort struggles with sorted and reverse sorted arrays because it often picks poor pivots, leading to highly unbalanced partitions and increased recursion depth, resulting in significantly slower times. In contrast, the median-of-three Quick Sort avoids this by selecting a pivot closer to the median, ensuring more balanced partitions and preventing worst-case O(n²) time complexity.

Conclusion

The median-of-three Quick Sort provides a substantial performance boost, especially for sorted and reverse-sorted arrays, as it mitigates worst-case scenarios by reducing partition imbalance. Its robustness on random arrays also stems from its more careful pivot selection, making it a versatile and consistently efficient option across different array types and sizes.

When to Use Quick Sort

Quick Sort is ideal when:

1. You need a fast, in-place sorting algorithm: With O(n log n) average-case time complexity and in-place sorting, Quick Sort is great for large datasets where memory usage matters.
2. Random or unsorted data: Quick Sort works well with data that does not have a clear ordering, as its performance is generally consistent.
3. You need general-purpose sorting: Quick Sort is widely used in practical applications because of its speed and versatility.

However, for datasets that are already sorted or nearly sorted, Merge Sort or Insertion Sort might be a better choice due to Quick Sort’s poor performance in its worst case.

Rust-Specific Considerations for Quick Sort

Implementing Quick Sort in Rust involves language features that affect performance and development. This section covers key Rust-specific considerations.

1. Ownership and Borrowing

Rust’s ownership system can be both a benefit and a challenge when implementing Quick Sort:

• Benefit: Rust ensures memory safety by enforcing strict rules around ownership and borrowing, which helps prevent issues such as dangling pointers and data races. When writing Quick Sort, you work with mutable slices (&mut [i32]), which means that Rust ensures no other program parts can modify the slice while it is sorted.
• Challenge: The ownership model can feel restrictive, especially if you come from other languages where passing references or pointers to arrays is more flexible. You must be careful in Rust when passing and modifying data between functions.

2. In-Place Mutation

Rust’s mutable borrowing allows in-place modification of arrays, which is crucial for an efficient Quick Sort. Since slices are references to parts of an array, sorting them in-place avoids unnecessary memory allocations and reduces the overhead associated with copying data.

• Benefit: Rust’s slices are powerful because they allow for efficient in-place mutation of arrays. Since the standard library provides robust support for slices, this can significantly improve the performance of Quick Sort.

3. No Built-In Tail Call Optimization

Rust does not guarantee tail call optimization (TCO), which means that recursive function calls are not automatically optimized to avoid using additional stack space. Since Quick Sort is recursive, deeply nested recursive calls could lead to stack overflow for large arrays, especially if the partitioning results in unbalanced subarrays (e.g., when sorting already sorted or reverse-sorted arrays).

• Challenge: If recursion depth becomes too large (due to poor pivot choices), it can cause a stack overflow. Strategies like median-of-three pivot selection are important to reduce the chances of deep recursion.
• Workaround: If stack overflows are a concern, you can switch to an iterative version of Quick Sort or set a recursion depth limit at which the algorithm switches to a non-recursive sorting algorithm (e.g., Insertion Sort).

4. Iterators and Functional Programming

Rust’s iterator API is a powerful tool that can simplify many operations on arrays and slices. For example, the partition function could potentially use iterators to improve readability or performance by eliminating the need for explicit loops.

• Benefit: Rust’s functional style with iterators can make the code more expressive and concise. For example, iterators can scan for elements that should be swapped during partitioning.
• Challenge: While iterators can improve readability and reduce boilerplate code, they may introduce overhead in performance-critical algorithms like Quick Sort. In many cases, manually optimizing loops may be faster.

5. Memory Safety and Concurrency

Rust’s emphasis on memory safety without a garbage collector allows for more predictable performance. In addition, Rust’s concurrency model, based on the concept of ownership, allows you to safely parallelize your Quick Sort implementation without worrying about data races.

• Benefit: If you want to parallelize Quick Sort, Rust’s rayon crate can help. It provides an easy way to implement parallelism while ensuring thread safety. This can significantly speed up large arrays by sorting the left and right partitions in parallel.

6. Standard Library Functions

Rust’s standard library provides a highly optimized sort function using a hybrid algorithm similar to TimSort. This raises an important question: when should you implement Quick Sort yourself?

• Challenge: In practice, Rust’s built-in sort function is already highly optimized, and it may be faster than a custom Quick Sort implementation in many cases. However, implementing Quick Sort is still valuable in understanding sorting algorithms and recursion.
• Benefit: You can use the built-in sort_unstable function in Rust’s standard library performs an unstable sort (i.e., it does not preserve the relative order of equal elements). This function is based on Quick Sort and is optimized for speed.

Conclusion

Quick Sort is a highly efficient sorting algorithm using a divide-and-conquer approach, making it ideal for a wide range of input types. In this post, we explored two key implementations: the original Quick Sort and the median-of-three version, comparing their performance across different array sizes and configurations. While the original Quick Sort performs well on random arrays, it struggles with sorted or reverse-sorted data due to poor pivot selection, often leading to unbalanced partitions and slower execution times.

The median-of-three Quick Sort addresses these shortcomings by selecting a more balanced pivot, improving performance on sorted, reverse-sorted, and large random arrays. We also examined specific optimizations like using Insertion Sort for small sub-arrays, tail call optimization to manage recursion depth, and hybrid algorithms like IntroSort to prevent worst-case scenarios. Ultimately, the median-of-three Quick Sort emerged as the more robust and versatile option, providing consistent performance improvements across different input scenarios and array sizes, making it a solid choice for optimizing sorting tasks in Rust.

Congratulations on reading to the end of the tutorial!

Read the following articles to learn how to implement Quick Sort:

In Python – How to do Quick Sort in Python

In C++ – How to Do Quick Sort in C++

Have fun and happy researching!