Merge Sort is one of the Most Important Algorithms according to RISC.

Here’s how Merge Sort works:

1. Divide the unsorted list into two sublists of about half the size
2. Sort each of the two sublists
3. Merge the two sorted sublists back into one sorted list.

In this case, “Merge” means to combine two (or more) sorted lists into one sorted list. Basically it will look at the first remaining item in each list and put the smaller one into a new list until both lists are consumed.

Because step 2 requires Merge Sort to sort the two sublists, this type of sort can be implemented recursively. The Merge Sort will stop calling itself recursively when the input list is only one item. Here’s a visualization:

 Step 1: sorted = msort{5, 9, 3, 2, 6, 1}
 
 Step 2: sorted = merge(msort{5, 9, 3}, msort{2, 6, 1})
 
 Step 3: sorted = merge({5}, msort{9,3}, {2}, msort{6,1})
 
 Step 4: sorted = merge({5}, {3,9}, {2}, {1,6})
 
 Step 5: sorted = merge({3,5,9}, {1,2,6})
 
 Step 6: sorted = {1,2,3,5,6,9}
 

At Step 4, we have 4 sorted sublists that we can merge into one sorted list.

This sort is, in the worst case, O(n log n), which is about as good as it gets for general-use sorting algorithms.

Here’s a PHP implementation of a mergeSort function, and you can view a demo of it here.

 	// divide and conquer recursive merge sort algorithm
 	function mergeSort($aList)
 	{
 		if(count($aList) == 1) {
 			return($aList);
 		} else {
 			$halfsize = ceil(count($aList) / 2);
 			$splitList = array_chunk($aList, $halfsize);
 
 			$left = $splitList[0];
 			$right = $splitList[1];
 			return(mergeList(mergeSort($left),mergeSort($right)));
 		}
 	}
 
 	// merge two sorted lists into one sorted list
 	// I think PHP might have a built-in function to do this
 	function mergeList($firstList,$secondList)
 	{
 		$i = 0;
 		$j = 0;
 		$resultList = array();
 		while(($i < count($firstList)) && ($j < count($secondList)))
 		{
 			if($firstList[$i] < $secondList[$j]) {
 				array_push($resultList,$firstList[$i]);
 				$i++;
 			} else {
 				array_push($resultList,$secondList[$j]);
 				$j++;
 			}
 		}
 
 		while($i < count($firstList))
 		{
 			array_push($resultList,$firstList[$i]);
 			$i++;
 		}
 		
 		while($j < count($secondList))
 		{
 			array_push($resultList,$secondList[$j]);
 			$j++;
 		}
 		return($resultList);
 	}