Complete Guide to Merge Sort: Implementation in Rust
When learning sorting algorithms, Merge Sort is an essential topic that cannot be overlooked. Today, we’ll dive deep into this efficient algorithm that uses the Divide and Conquer strategy, implementing it in Rust to understand its principles thoroughly.
What is Merge Sort? Merge Sort is a stable sorting algorithm with O(n log n) time complexity. It follows the divide-and-conquer paradigm and operates in three distinct steps: 1. Divide Split the array in half. Calculate the midpoint q and divide array A[p:r] into A[p:q] and A[q+1:r]. rust let q = (p + r) / 2; // Calculate midpoint 2. Conquer Recursively sort each of the two subarrays. rust merge_sort(arr, p, q); // Sort left half merge_sort(arr, q + 1, r); // Sort right half 3. Combine Merge the two sorted subarrays to produce a fully sorted array. rust merge(arr, p, q, r); // Merge The Core: merge Function Implementation The heart of Merge Sort is the merge function. Let's examine the process of combining two already-sorted arrays into one sorted array. Step-by-Step Analysis Step 1: Create Temporary Arrays rust let nl = q - p + 1; // Left array size let nr = r - q; // Right array size
let mut l_arr: Vec<i32> = vec![0; nl as usize]; let mut r_arr: Vec<i32> = vec![0; nr as usize]; Create temporary arrays to hold the left and right portions. Step 2: Copy Data rust for i in 0..nl {
l_arr[i as usize] = arr[(p + i) as usize];
} for j in 0..nr {
r_arr[j as usize] = arr[(q + j + 1) as usize];
} Copy data from the original array into temporary arrays. Step 3: Merge rust let mut i = 0; // Left array index let mut j = 0; // Right array index let mut k = p; // Original array index
while i < nl && j < nr {
if l_arr[i as usize] <= r_arr[j as usize] {
arr[k as usize] = l_arr[i as usize];
i += 1;
} else {
arr[k as usize] = r_arr[j as usize];
j += 1;
}
k += 1;
} Compare elements from both arrays and place the smaller value into the original array in order. Step 4: Handle Remaining Elements rust while i < nl {
arr[k as usize] = l_arr[i as usize]; i += 1; k += 1;
}
while j < nr {
arr[k as usize] = r_arr[j as usize]; j += 1; k += 1;
} When one array is exhausted, copy all remaining elements from the other array. Visualization Example The process of sorting the array [3, 41, 52, 26, 38, 57, 9, 49]: [3, 41, 52, 26, 38, 57, 9, 49]
↓ Divide
[3, 41, 52, 26] [38, 57, 9, 49]
↓ ↓
[3, 41] [52, 26] [38, 57] [9, 49]
↓ ↓ ↓ ↓
[3] [41] [52] [26] [38] [57] [9] [49]
↓ ↓ ↓ ↓
[3, 41] [26, 52] [38, 57] [9, 49]
↓ ↓
[3, 26, 41, 52] [9, 38, 49, 57]
↓ Merge
[3, 9, 26, 38, 41, 49, 52, 57] Time Complexity Analysis
- Best, Average, and Worst cases: O(n log n)
- Divide: O(log n) — splitting the array in half
- Merge: O(n) — comparing all elements once
- Overall: O(n log n)
Space Complexity
- O(n) — additional memory equal to the original array size is needed during merging
Pros and Cons Advantages
- Stable Sort: maintains relative order of equal elements
- Predictable Performance: always O(n log n)
- Efficient for linked lists
Disadvantages
- Requires Extra Memory: O(n) space complexity
- Overhead may be significant for small arrays
Execution Result rust pub fn example() {
let mut arr = vec![3, 41, 52, 26, 38, 57, 9, 49];
let n = &arr.len();
merge_sort(&mut arr, 0, (n - 1) as i32);
println!("{:?}", arr);
} // Output: [3, 9, 26, 38, 41, 49, 52, 57] All Code /* Merge Sort (O(n log n)) - Divide and Conquer algorithm
Divide - Split the subarray A[p:r] into two adjacent subarrays of roughly equal size.
Compute the midpoint q of (p+r)/2.
- Divide A[p:r] into A[p:q] and A[q+1:r].
Conquer - Recursively sort the two subarrays A[p:q] and A[q+1:r] using merge sort.
Combine - Merge the two sorted subarrays A[p:q] and A[q+1:r] into a single sorted array A[p:r].
- /
fn merge(arr: &mut Vec<i32>, p: i32, q: i32, r: i32) {
let nl = q - p + 1; // size of A[p:q] let nr = r - q; // size of A[q+1:r]
// Create arrays L[0:nl-1] and R[0:nr-1] let mut l_arr: Vec<i32> = vec![0; nl as usize]; let mut r_arr: Vec<i32> = vec![0; nr as usize];
for i in 0..nl {
// Copy A[p:q] into L[0:nl-1]
l_arr[i as usize] = arr[(p + i) as usize];
}
for j in 0..nr {
// Copy A[q+1:r] into R[0:nr-1]
r_arr[j as usize] = arr[(q + j + 1) as usize];
}
let mut i = 0; // index for remaining smallest element in L let mut j = 0; // index for remaining smallest element in R let mut k = p; // index for placing element into A
// Merge L and R into A[p:r]
while i < nl && j < nr {
if l_arr[i as usize] <= r_arr[j as usize] {
arr[k as usize] = l_arr[i as usize];
i += 1;
} else {
arr[k as usize] = r_arr[j as usize];
j += 1;
}
k += 1;
}
// Copy remaining elements from L (if any)
while i < nl {
arr[k as usize] = l_arr[i as usize];
i += 1;
k += 1;
}
// Copy remaining elements from R (if any)
while j < nr {
arr[k as usize] = r_arr[j as usize];
j += 1;
k += 1;
}
}
fn merge_sort(arr: &mut Vec<i32>, p: i32, r: i32) {
// If subarray has 0 or 1 elements, it's already sorted
if p >= r {
return;
}
let q = (p + r) / 2; // midpoint of [p:r]
merge_sort(arr, p, q); // Sort A[p:q] recursively merge_sort(arr, q + 1, r); // Sort A[q+1:r] recursively merge(arr, p, q, r); // Merge A[p:q] and A[q+1:r] into A[p:r]
}
pub fn example() {
let mut arr = vec![3, 41, 52, 26, 38, 57, 9, 49];
let n = arr.len();
merge_sort(&mut arr, 0, (n - 1) as i32);
println!("{:?}", arr);
} Conclusion Merge Sort is a quintessential algorithm that demonstrates the elegance of divide-and-conquer. Despite requiring additional memory, its stability and predictable performance make it widely used in production environments. Rust’s type safety and ownership system enable safe implementation of complex algorithms like Merge Sort. By directly handling recursion and memory management, you can gain a deep understanding of the algorithm.