# Mergesort implemented in rust language

## Intro

In this article, I've explained how mergesort works and also provided an implementation in rust language.

## Mergesort Algorithm

Mergesort it's another divide-and-conquer algorithm similar to quicksort. The algorithm consists of two steps:

Divide the array to be merged into halves till the resulting array it's of size one.

The second step is to apply bottom up

`merging`

procedure which works as follow:we compare the first element from each array to be merged; the smallest will be included in a new merged array, and removed from the partitioned array.

we repeat the procedure till there are no more elements in any of the arrays to be merged.

## Analysis

Time complexity of `mergesort`

is `O(nlogn)`

in all cases. Space complexity is `O(n)`

we will need an extra array to store the merged parts from left and right.

## Implementation in rust

```
pub fn mergesort<T: PartialOrd + Copy>(arr: &mut [T]) {
_mergesort(arr, 0, arr.len() - 1);
}
```

```
fn _mergesort<T: PartialOrd + Copy>(arr: &mut [T], left: usize, right: usize) {
if left < right {
let mid = (left + right) / 2;
_mergesort(arr, left, mid);
_mergesort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
```

```
fn merge<T: PartialOrd + Copy>(arr: &mut [T], left: usize, mid: usize, right: usize) {
let left_arr = &arr[left..=mid].to_owned();
let right_arr = &arr[mid + 1..=right].to_owned();
let mut i = 0;
let mut j = 0;
for k in left..=right {
if i < left_arr.len() && j < right_arr.len() {
if left_arr[i] < right_arr[j] {
arr[k] = left_arr[i];
i += 1;
} else {
arr[k] = right_arr[j];
j += 1;
}
} else if i >= left_arr.len() {
arr[k] = right_arr[j];
j += 1;
} else {
arr[k] = left_arr[i];
i += 1;
}
}
}
```