#Merge Sort
##Why Merge Sort?
Merge sort is one of the most powerful sorting algorithms that you will encounter. In fact it is the native .sort algorithm used in many JavaScript environments (such as Mozilla's). It compares a list of elements using a "Divide and Conquer" strategy.
What's the main purpose of sorting your data?
##How does it work? Merge Sort works on the basic principal of dividing a list into sub-lists until your sub-lists are of length one or zero. Once your sub-lists are at that size, you merge with a neighboring sub-list. Note, lists of size one are techinically already sorted.
What do you think the runtime of this algorithm would be?
##Visualizations
Exercise: can we act it out?
##How would I build it?
- A
mergeSortfunction may take an array, cut it in half recursively until it has divided the whole array into single items. At this point the recursive calls finally starts returning to the function that invoked it. At this point a separate helper function,merge, could be called on a pair of sorted arrays merging them together (see visualization above). - The
mergefunction takes two sorted arrays as parameters (an array with one element is technically sorted), looks at the the first elements of the two lists, and assembles a resulting list based on the two lists "zipped" together by pushing the lowest to highest valued elements.
##Drill
Pseudocode an implementation of merge.
Bonus: Pseudocode an implementation of mergeSort.