Merge Sort is an algorithm that has a fairly efficient space time complexity - O(n log n) and is fairly trivial to implement. The algorithm is based on splitting a list, into two similar sized lists (left, and right) and sorting each list and then merging the sorted lists back together.
Note: the function MergeOrdered simply takes two ordered lists and makes them one.
Merge Sort follows the rule of Divide and Conquer. In merge sort the unsorted list is divided into N sublists, each having one element, because a list consisting of one element is always sorted. Then, it repeatedly merges these sublists, to produce new sorted sublists, and in the end, only one sorted list is produced.
Merge Sort is quite fast and is also a stable sort, which means the “equal” elements are ordered in the same order in the sorted list.
That’s it for this one !!!