Merge sort was developed to handle the sorting of large lists. By breaking them down into smaller lists, sorting them, and then merging them back together into one larger list
Merge sort keeps carrying out the same action until an end condition is met, then it reverses again. This suggests that a recursive approach would be an efficient way of doing this. Let there be an unsorted list
WHILE there remains an unsorted list
Function: Split each list in two # this is a recursive call
IF every list is 1 or less in length THEN exit
END WHILE
# at this stage every list is either 1 or zero in length
# which means by definition they are sorted
# Now merge and sort each list pair
WHILE there is more than one list
Function: Sort and combine lists # this is a recursive call
END WHILE
For merge sort, the splitting part of the algorithm repeatedly divides the list in half no matter how ordered or unordered the items are. The best-case scenario is when the algorithm performs the smallest possible number of comparisons during the merging stages.
The worst-case scenario takes place when the list of items you are sorting results in the greatest possible number of comparisons. For merge sort, this occurs during the merging stages. Consider how two sublists are merged together. The worst-case scenario occurs when every item needs to be compared in turn, until there is only one item left in each sublist for the final comparison.Best, worst and average time complexity - O(nlogn)
Space complexity - O(n)