Table of content

Merge sort in Rust

Mergesort is a general-purpose, efficient and stable sorting method with best and worst time complexity of $O(n log n) $.

Mergesort is a classic example of the famous "Divide and Conquer" technique. It first divides the sequence into smaller sub-sequences (Divide), sorts one by one (Conquer), and then merges the sorted sub-sequences (Combine).

  • Efficient and stable : the best, average, and worst time complexity are $O(n log n) $.
  • Stable sorting : Elements of the same key value, the relative position does not change after sorting.
  • Non-in-place sorting : In addition to the data itself, additional storage space is required to sort.
  • Divide and Algorithm : The main problem is turned into several sub-problems, each broken.
Steps

The Mergesort algorithm is divided into the following steps:

  • Divide : Splits a sequence containing n elements into n / 2 subsequences.
  • Conquer : Sorts the two subsequences after segmentation.
  • Combine : merges the two subsequences that have been sorted into a sorted sequence.

Among them, the "sort" in the Conquer step can be continuously returned to the Mergesort itself, so we need to stop the base case. We set the condition to "the length of the subsequence is less than 2" because the sequence of length 1 can be regarded as Sorting has been completed.

/// Mergesort.

/// - Top-down

/// - Recursive

pub fn mergesort(arr: &mut [i32]) { let mid = arr.len() / 2; if mid == 0 { return; }

mergesort(&mut arr[..mid]); mergesort(&mut arr[mid..]);

// Create an array to store intermediate result. let mut ret = arr.to_vec();

// Merge the two piles. merge(&arr[..mid], &arr[mid..], &mut ret[..]);

// Copy back the result back to original array. arr.copy_from_slice(&ret); }

/// Mergesort bottom-up version.

/// - Buttom-up (for array-based data structure)

/// - Iterative
pub fn mergesort_bottom_up(arr: &mut [i32]) { let mut width = 1; // Create an array to store intermediate result. let mut ret = arr.to_vec(); let len = arr.len();

while width < len { let mut i = 0; while i < len { // Check to avoid upper bound and middle index out of bound. let upper = ::std::cmp::min(i + 2 * width, len); let mid = ::std::cmp::min(i + width, len);

merge(&arr[i..mid], &arr[mid..upper], &mut ret[i..upper]);

// Copy the merged result back to original array. arr[i..upper].copy_from_slice(&ret[i..upper]);

// Increase start index to merge next two subsequences. i += 2 * width; } width *= 2; } }

/// Merge helper.

/// * `arr1` - Left pile to sort.

/// * `arr2` - Right pile to sort.

/// * `ret` - Result array to return

fn merge(arr1: &[i32], arr2: &[i32], ret: &mut [i32]) { let mut left = 0; // Head of left pile. let mut right = 0; // Head of right pile. let mut index = 0;

// Compare element and insert back to result array. while left < arr1.len() && right < arr2.len() { if arr1[left] <= arr2[right] { ret[index] = arr1[left]; index += 1; left += 1; } else { ret[index] = arr2[right]; index += 1; right += 1; } }

// Copy the reset elements to returned array. // `memcpy` may be more performant than for-loop assignment. if left < arr1.len() { ret[index..].copy_from_slice(&arr1[left..]); } if right < arr2.len() { ret[index..].copy_from_slice(&arr2[right..]); } }

#[cfg(test)]

mod base { use super::*; base_cases!(mergesort); }

#[cfg(test)]

mod bottom_up { use super::*; base_cases!(mergesort_bottom_up); }

Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions