MergeSort - Eishaaya/GMRDataStructuresTest GitHub Wiki
Merge sort is a divide-and-conquer algorithm with a worst-case running time of O(n*log2(n)). As the divide and conquer paradigm might suggest, merge sort divides the problem into smaller sub-problems then combines the results to produce a sorted array. The recursive sequence is broken when the size of the problem (or the array) is less than 2. Once the base case is met, the sub-arrays begin merging while maintaining a sorted order. Hence, they are conquered.
There are two methods that help accomplish merge sort. The first method, MergeSort, is what divides the input list. The recursive calls are done here. The second method, Merge, is what combines the sub-lists. The sorting is done here. To generate the two sub lists (left and right), you must calculate the midpoint of the given input list and add everything from the beginning to the midpoint (exclusive) to the first (left) list, and everything from the midpoint (inclusive) to the end of the list to the second (right) sub list. Then call the MergeSort function on the first sub-list, followed by a the same call on the second sub-list. Then we make a call to the Merge function which will take in the left sub-list, right sub-list, and the original list to hold the sorted values. The following will summarize what they are and how they might be implemented:
MergeSort (Recursive):
- Args:
List<T> - Return:
void - Split the input list into two sub-lists (left and right). If the input list cannot be split (size < 2), return.
- Recursively sort each sub-list.
- Merge the two sorted sub-lists and add the smaller of the two values from the sub lists into the final list, don't forget to add the remainder of a list if they are of uneven sizes.
Added Challenge:
After implementing MergeSort, modify it to utilize the Queue data structure.
Applications:
Merge sort is one of a few stable sorting algorithms with a running time of O(n*log2(n)). A stable algorithm preserves the order of the elements that have equal values. For example, if two integers have the same value in an array, they will be in the same order even after a merge sort has been performed on the array. This is especially useful when data can be sorted with different keys. In Spotify, songs a playlist can first be sorted by artist and then by album. When sorting by album, songs with the same album name will be in the same order relative to each as they were when sorted by artist.
A disadvantage of merge sort is that it requires memory of size n, where n is the size of the input. When memory is a definite constraint, quick sort is a better option.
- Take a look at our implementation if you are stuck.