Merge Sort Algorithm in Rust Codes

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.

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.

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;
    }
}

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.

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);

}

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.

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);
}

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, 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]

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.

2 Rust Functions for Merge Sort

Merge Rust Function

Merge_sort Rust Function

Merge Sort Algorithm in Rust Demo

Other Algorithms in Rust

Related Articles

You Might Also Like

Search the site