In an effort to refresh my mind with the MergeSort algorithm, I wrote the code below. I found an extremely intuitive explanation of MergeSort algorithm in the Introduction to Algoirthms By: Cormen, Leiserson, Rivest. Bare with me while I attempt to summarize this intuition in "plain English" ```Imagine two arrays A, B with sorted integers in each: A B [0]3 [0]55 [1]4 [1]73 [2]99 How can we systematically make a third array, that will be the Union of array A and B while at the same time maintaining the sorted property? Lets look at a pretty simple algorithm, called MergeSort :) 1. Look at the element in the top most index of both arrays: 'A' 'B' -->[0]3 -->[0]55 [1]4 [1]73 [2]99 Its 3, and 55. 3 Is smaller then 55, so we POP 3 off array A and insert into the NEW merged array we are going to call 'C'. Now things look like they do below: 'A' 'B' 'C' [0]4 [0]55 [0]3 [1]73 [2]99 We continue to look at the "CURRENT" top most index and make a comparison again. 'A' 'B' 'C' -->[0]4 -->[0]55 [0]3 [1]73 [2]99 Its 4 and 55. 4 is smaller so it gets POPPED of array 'A' and inserted into next available slot of array 'C'. Now things look like they do below. ' A' 'B' 'C' (empty) [0]55 [0]3 [1]73 [1]4 [2]99 At this point array 'A' is empty. That's even better for us, since we dont need to make any more comparisons! Simply move all the elements of 'B' (STARTING with the top most index) onto the end of array 'C'. Now things look like they do below. ' A' 'B' 'C' (empty) (empty) [0]3 [1]4 [2]55 [3]73 [4]99 MergeSort works recursively by first breaking the input array into halfs, then performing the above algorithm in each recursive level, and finally passing the resulting SORTED array to the levels above. The code below demonstrates this idea. Notice recursion stops when array size is equal to one. Performing the merge algorithm described above on two arrays with one element in each is trivial. ``` Program Entry Point /*MergeSort - By: Vladimir Sutskever  */ using System; using System.Collections.Generic; using System.Text; using System.Collections; namespace MergeSort {     class Program {         static void Main ( string[] args ) {             MergeSorter oSorter = new MergeSorter();             //--------------------------------------             //Create Array List, add some numbers             //--------------------------------------             ArrayList arrayUnsorted= new ArrayList();             arrayUnsorted.Add(1);             arrayUnsorted.Add(33);             arrayUnsorted.Add(4);             arrayUnsorted.Add(43);             //--------------------------------------             //Sort             //--------------------------------------             ArrayList arraySorted = oSorter.MergeSort(arrayUnsorted);             //--------------------------------------             //Print             //--------------------------------------             foreach (int i in arraySorted) {                 Console.WriteLine(i);             }                      }     } } Sorter Class /*MergeSort - By: Vladimir Sutskever  */ using System; using System.Collections.Generic; using System.Text; using System.Collections; namespace MergeSort {     class MergeSorter {         //==================================================         //Constructor         //==================================================         public MergeSorter(){         }         //==================================================         // MergeSort         //==================================================         public ArrayList MergeSort ( ArrayList arrIntegers ) {             if (arrIntegers.Count == 1) {                 return arrIntegers;             }             ArrayList arrSortedInt = new ArrayList();             int middle = (int)arrIntegers.Count/2;             ArrayList leftArray = arrIntegers.GetRange(0, middle);             ArrayList rightArray = arrIntegers.GetRange(middle, arrIntegers.Count - middle);             leftArray =  MergeSort(leftArray);             rightArray = MergeSort(rightArray);             int leftptr = 0;             int rightptr=0;             for (int i = 0; i < leftArray.Count + rightArray.Count; i++) {                 if (leftptr==leftArray.Count){                     arrSortedInt.Add(rightArray[rightptr]);                     rightptr++;                 }else if (rightptr==rightArray.Count){                     arrSortedInt.Add(leftArray[leftptr]);                     leftptr++;                 }else if ((int)leftArray[leftptr]<(int)rightArray[rightptr]){                     //need the cast above since arraylist returns Type object                     arrSortedInt.Add(leftArray[leftptr]);                     leftptr++;                 }else{                     arrSortedInt.Add(rightArray[rightptr]);                     rightptr++;                 }             }             return arrSortedInt;         }     } }