As we already know that merge sort applies the divide-and-conquer approach to solve the sorting problem, we need to find out two processes to address the issue. The first one is to divide the problem set into smaller enough problems to solve easily, and then combine those results. We will apply a recursive approach here for the divide-and-conquer part. The following image shows how to take the approach for divide-and-conquer. We will now consider a smaller list of numbers 20, 45, 93, 67, 97, 52, 88, 33 to explain the divide-and-conquer part:
Based on the preceding image, we can now start preparing our pseudocode, which will have two parts - divide and conquer. Here is the pseudocode to achieve that
func mergesort ( A : array of sortable items):
n = length(A)
if ( n == 1 ) return a
var l1 as...