Created: July, 15, 2023 Last Modified: July, 16, 2023
What Is Merge Sort
Merge Sort is a divide-and-conquer sorting algorithim. This is done by splitting the list into 2 and then continously spliting those lists, until we end up with many 1 length lists. Which are then merged and return to be merged with the other splits. Merge sort is O(n log n)
Merge Sort is good for large list sorting, but can be slower for smaller lists
Quick note: rust actaully has sorting implemented as a trait, vectors can be sorted by calling .sort() on them.
Implementing Merge Sort With Generics, The Merge Part
Merge Sort can seperated into two functions. A merge function that takes two lists and merges them, sorting (in this case smallest to largest); And the main function its self, merge_sort, which will be recursivly called finally calling merge at the end.
Merge compares two lists and takes the smaller value, moving to the next element in list that contained the smaller value. once a list is exhausted the rest of the other list is appended to the end of the out list, if both are exhausted then the out list is returned. Thanks to the Rust Trait system we can write this once as a generic implmentation and get it for all types that have the ParialOrd and Clone trait. ParitalOrd is needed for Comparing the values contained in the vector
The Merge Sort Part
Now we can write the whole merge sort function. Merge sort should return the passed list if the size is less than 2. Otherwise it should split the list and call mergesort and both. Lastly calling merge and returning the resulting list.
With that you now have a merge sort function ready to sort all of your vectors. The full code can be seen below
Full Code can be found at https://github.com/PGIII/rust-algos/blob/main/src/merge_sort.rs