Last Updated on

This post is about the Merge Sort algorithm in Rust codes. Merge Sort is an algorithm invented by John von Neumann in 1945 and it’s one of the most efficient sorting algorithms. It uses the principle of divide-and-conquer.

Contents

## 2 Rust Functions for Merge Sort

We have Rust codes that use 2 functions because it uses iteration and recursion. The recursive codes split the list of elements into sub-lists; on the other hand, the iterative codes sort each sub-list’s items and combine it to other sub-lists and so on.

### Merge Rust Function

This **merge** function merges sorted portions of the original array.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
fn merge(ori: &mut [i32], copy: &mut [i32], low: usize, mid: usize, high: usize) { let mut x = low; let mut y = low; let mut z = mid + 1; while y <= mid && z <= high { if ori[y] < ori[z] { copy[x] = ori[y]; x+=1; y+=1; } else { copy[x] = ori[z]; x+=1; z+=1; } } while y <= mid { copy[x] = ori[y]; x+=1; y+=1; } y = low; while y <= high { ori[y] = copy[y]; y+=1; } } |

### Merge_sort Rust Function

This function recursively divides the list of elements. The smallest lists contain 2 elements.

1 2 3 4 5 6 7 8 9 10 11 12 |
fn merge_sort(ori: &mut [i32], copy: &mut [i32], low: usize, high: usize) { if high == low { return; } let mut mid: usize = (low + (( high - low ) >> 1)); merge_sort(ori, copy, low, mid); merge_sort(ori, copy, mid + 1, high); merge(ori, copy, low, mid, high); } |

## Merge Sort Algorithm in Rust Demo

Here we have 2 arrays **ori** and **copy** that hold the original items and the sorted items, respectively. The **copy** has the initial values of zeros. After line 4, it will have values as **ori**.

1 2 3 4 5 6 7 8 9 10 11 12 |
fn main() { let mut ori:[i32; 13] = [1, 0, 9, 8, 100, 345, 5, 6,7 , 4, 3, 2, 1]; let mut copy:[i32; 13] = [0; 13]; copy.clone_from_slice(&ori); println!("{:?}",ori); let len:usize = ori.len() - 1; merge_sort(&mut ori, &mut copy, 0, len); println!("{:?}",ori); } |

The merge_sort function accepts 4 arguments – the 2 arrays; and indices 0 and len. The indices help in determining at which indices to break an array into sub-arrays.

Output

1 2 |
[1, 0, 9, 8, 100, 345, 5, 6, 7, 4, 3, 2, 1] [0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 100, 345] |

Tested with Rust 1.38.0.

## Other Algorithms in Rust

For more algorithms in Rust, please go to Algorithms In Codes page.