## 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)**

**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.

- The function checks if
**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.

- The
**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.

- The

**Partition Function (Rearranges the Array Around the Pivot)**

**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.

- The pivot is usually selected as the last element (
**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.

- Set
**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.

- A loop runs from
**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.

- If the element at
**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.

- Swap
**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.

- After the loop ends, swap
**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`

.

- Compare
`34`

with`62`

. Since`34 <= 62`

, we swap`arr[i]`

with`arr[0]`

(which is`34`

itself). Then, we increment`i`

to`1`

. - Compare
`7`

with`62`

. Since`7 <= 62`

, we swap`arr[i]`

with`arr[1]`

(which is`7`

itself). Then, increment`i`

to`2`

. - Compare
`23`

with`62`

. Since`23 <= 62`

, we swap`arr[i]`

with`arr[2]`

(which is`23`

itself). Then, increment`i`

to`3`

. - Compare
`32`

with`62`

. Since`32 <= 62`

, we swap`arr[i]`

with`arr[3]`

(which is`32`

itself). Then, increment`i`

to`4`

. - 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`

.

- Compare
`34`

with`5`

. Since`34 > 5`

, no swap is made. - Compare
`7`

with`5`

. Since`7 > 5`

, no swap is made. - Compare
`23`

with`5`

. Since`23 > 5`

, no swap is made. - 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`

.

- Compare
`7`

with`34`

. Since`7 <= 34`

, we swap`arr[i]`

with`arr[0]`

(which is`7`

itself). Then, increment`i`

to`1`

. - Compare
`23`

with`34`

. Since`23 <= 34`

, we swap`arr[i]`

with`arr[1]`

(which is`23`

itself). Then, increment`i`

to`2`

. - 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:

**Compare**: Since`34`

and`23`

`34 > 23`

, we swap them. The array becomes`[23, 7, 34, 32, 5, 62]`

.**Compare**: Since`23`

and`62`

`23 < 62`

, no swap is needed.**Compare**: Since`34`

and`62`

`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`

:

**Compare**: Since`62`

and`34`

`62 > 34`

, decrement`high`

to`4`

.**Compare**: Since`5`

and`34`

`5 < 34`

, increment`low`

to`2`

.**Compare**: Since`23`

and`34`

`23 < 34`

, increment`low`

to`3`

.**Compare**: Since`32`

and`34`

`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:

**Compare**: Since`32`

and`7`

`32 > 7`

, we swap them. The array becomes`[7, 32, 23, 5]`

.**Compare**: Since`7`

and`5`

`7 > 5`

, we swap them. The array becomes`[5, 32, 23, 7]`

.**Compare**: Since`32`

and`7`

`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`

:

**Compare**: Since`32`

and`7`

`32 > 7`

, decrement`high`

to`2`

.**Compare**: Since`23`

and`7`

`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 first element is

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:

**Random Array**: An array filled with random integers.**Sorted Array**: An array in ascending order.**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:

**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.**Random or unsorted data**: Quick Sort works well with data that does not have a clear ordering, as its performance is generally consistent.**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!

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.