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.