Sorting

Merge Sort (Top-Down)

Split the array recursively, sort each half, then merge two sorted runs into one sorted result.

Algorithm

Basic Implementation

basic.rs 
fn merge_sort(values: &[i32]) -> Vec<i32> {
	if values.len() <= 1 {
		return values.to_vec();
	}
	let mid = values.len() / 2;
	let left = merge_sort(&values[..mid]);
	let right = merge_sort(&values[mid..]);
	let mut merged = Vec::new();
	let (mut i, mut j) = (0, 0);
	while i < left.len() && j < right.len() {
		if left[i] <= right[j] {
			merged.push(left[i]);
			i += 1;
		} else {
			merged.push(right[j]);
			j += 1;
		}
	}
	merged.extend_from_slice(&left[i..]);
	merged.extend_from_slice(&right[j..]);
	merged
}

fn main() {
	let arr = [5, 1, 4, 2, 8];
	println!("{:?}", merge_sort(&arr));
}

The pinned input is [5, 1, 4, 2, 8]. The diagrams show the split into recursive halves, the sorted subarrays, and the final merge choices.

Step 1 - Split the input

The first midpoint splits [5, 1, 4, 2, 8] into left [5, 1] and right [4, 2, 8].

Top-down split used by merge_sort.[5,1,4,2,8]mid = 2[5,1]left[4,2,8]right

Step 2 - Sorted halves return

Recursive calls return [1, 5] and [2, 4, 8] before the final merge begins.

Returned subarrays before the final merge.sidebefore sortafter sortleft[5, 1][1, 5]right[4, 2, 8][2, 4, 8]

Step 3 - Merge by taking smaller fronts

Take 1 from left, then 2 and 4 from right, then the remaining 5 and 8.

Final merge produces [1, 2, 4, 5, 8].choiceleft frontright frontmergedtake 112[1]take 252[1, 2]take 454[1, 2, 4]extend58[1, 2, 4, 5, 8]

Complexity

  • Time: O(n log n)
  • Space: O(n)
  • Stable: yes

Implementation notes

  • main starts with a fixed array, let arr = [5, 1, 4, 2, 8], and calls merge_sort(&arr), borrowing it as a slice.
  • The recursive signature is fn merge_sort(values: &[i32]) -> Vec<i32>, so calls read borrowed slices and return newly allocated vectors rather than sorting the original array in place.
  • The base case values.len() <= 1 returns values.to_vec(), copying the small slice into an owned Vec<i32>.
  • Splitting uses let mid = values.len() / 2, then borrows &values[..mid] and &values[mid..] for the recursive calls.
  • Merge state is held in let mut merged = Vec::new() and cursor indices (mut i, mut j). The comparison left[i] <= right[j] takes the left value first on ties, preserving stability.
  • Remaining elements are copied with extend_from_slice(&left[i..]) and extend_from_slice(&right[j..]); the returned merged vector is the sorted result.
  • The trace records the top split [5, 1] and [4, 2, 8], sorted halves [1, 5] and [2, 4, 8], then merged output [1, 2, 4, 5, 8].
  • println!("{:?}", merge_sort(&arr)) uses Rust's debug formatter for the returned Vec<i32> and prints [1, 2, 4, 5, 8].
divide and conquer Each recursive call solves a smaller sorted subproblem.
merge step Two sorted halves are combined by repeatedly taking the smaller front item.