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 array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end func
func merge( a: array, b : array )
c = array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
return c
end while
end func
Our first part of the pseudocode shows the divide process. We divided the array of items until it reaches the size of 1. Then, we started to merge the results using the merge function. In the merge function, we had an array to store the merged results. Because of this, merge sort actually has more space complexity than the other algorithms we have seen so far. Now, let's get into coding and implement this pseudocode using PHP.