Merge Sort<TITLE> </HEAD> <BODY> <P><CENTER><B><H1>Merge Sort</H1></B></CENTER> <P>The <U>Merge Sort</U> algorithm is a technique for sorting an array. It is a relatively efficient method which makes use of recursion. <P>Merge Sort is well suited to sorting data in files too large to fit into memory, which is not at all an unusual task. <P>If Merge Sort is coded properly, it is a <I>stable sort</I>, which is to say that the relative order of elements whose key fields are equal is preserved. <P>We will examine this in the case of "ascending order"; it works equally well for "descending order". <P><HR> <P><B>How does Merge Sort work?</B> <P>The idea of Merge Sort is as follows: <OL TYPE=1> <LI>We start with an array with subscripts starting at First and ending at Last, where First <= Last. <P> <LI>If First is equal to Last, there is nothing to do. <P> <LI>Otherwise we do the following: <OL TYPE=A> <LI>Set Middle = (First + Last) / 2. <P> <LI>Call Merge Sort recursively with subscripts First and Middle. <P> <LI>Call Merge Sort recursively with subscripts Middle+1 and Last. <P> <LI>Call the Merge function, passing it the array and the values of First, Middle and Last. </OL> </OL> <P><HR> <P><B>What does the function Merge do?</B> <P>The merge function works with the array in two parts, a left part from subscript First to subscript Middle and a Right part from subscript Middle+1 to Last. By the time Merge is called, each of these sub-arrays has already been sorted. Merge will combine the two arrays into one. <P>To simplify the discussion, we will assume we have a spare array called Spare. It is possible to write the code to sort the array in place, that is, without needing a spare array. <P>Pseudocode for the Merge Function is as follows: <PRE> Set I = First Set J = Middle+1 Set K = 0 While I < Middle+1 and J < Last+1 If Array[I] <= Array[J] Set Spare[K] = Array[I] Add 1 to I Add 1 to K Else Set Spare[K] = Array[J] Add 1 to J Add 1 to K End-If End-While While I < Middle+1 Set Spare[K] = Array[I] Add 1 to I Add 1 to K End-While While J < Last+1 Set Spare[K] = Array[J] Add 1 to J Add 1 to K End-While Set I = First Set K = 0 While I < Last+1 Set Array[I] = Spare[K] Add 1 to I Add 1 to K End-While</PRE> <P><HR> <P><B>How fast is Merge Sort?</B> <P>For an array of N elements, Merge Sort uses a number of steps proportional to N * log(N). <P><HR> <P><B>What does this look like in C++?</B> <P>Here is a program implementing Merge Sort. It prints out some information to point out what is happening at any moment. <PRE>#include <iostream> #include <iomanip> #define SIZE 8 using std::cout; using std::endl; using std::setw; void MSort(int A[], int Temp[], int Left, int Right, int Level); void Merge(int A[], int Temp[], int Left, int Right); void Indent(int); int main() { int H[SIZE] = { 32, 12, 34, 54, 6, 56, 76, 8}; int Temp[SIZE]; cout << "Level = 0: main program." << endl; cout << "The unsorted array is: "; for (int I = 0; I < SIZE; I++) cout << setw(4) << H[I]; cout << endl << endl; MSort(H, Temp, 0, SIZE - 1, 1); cout << "Level 0: main program." << endl; cout << "The sorted array is: "; for (int I = 0; I < SIZE; I++) cout << setw(4) << H[I]; cout << endl << endl; } void MSort(int A[], int Temp[], int Left, int Right, int Level) { int Middle, G, H; Indent(Level); cout << "Level = " << Level << ": Start of call to MSort with Left = " << Left << " and Right = " << Right << endl; Indent(Level); cout << "The partially sorted array is: "; for (G = Left; G <= Right; G++) cout << setw(4) << A[G]; cout << endl << endl; if (Left < Right) { Middle = (Left + Right) / 2; MSort(A, Temp, Left, Middle, Level+1); MSort(A, Temp, Middle+1, Right, Level+1); Merge(A, Temp, Left, Right); } Indent(Level); cout << "Level = " << Level << ": End of call to MSort with Left = " << Left << " and Right = " << Right << endl; Indent(Level); cout << "The sorted array is: "; for (G = Left; G <= Right; G++) cout << setw(4) << A[G]; cout << endl << endl; } void Merge(int A[], int Temp[], int Left, int Right) { int I, J, K, Middle; Middle = (Left + Right) / 2; K = 0; I = Left; J = Middle+1; while (I <= Middle && J <= Right) if (A[I] <= A[J]) { Temp[K] = A[I]; I++; K++; } else { Temp[K] = A[J]; J++; K++; } while (I <= Middle) { Temp[K] = A[I]; I++; K++; } while (J <= Right) { Temp[K] = A[J]; J++; K++; } K = 0; I = Left; while (I <= Right) { A[I] = Temp[K]; I++; K++; } } void Indent(int Level) { int H; for (H = 0; H < 2*Level-1; H++) cout << ' '; }</PRE> <P>Here is the output from running the above program: <PRE>Level = 0: main program. The unsorted array is: 32 12 34 54 6 56 76 8 Level = 1: Start of call to MSort with Left = 0 and Right = 7 The partially sorted array is: 32 12 34 54 6 56 76 8 Level = 2: Start of call to MSort with Left = 0 and Right = 3 The partially sorted array is: 32 12 34 54 Level = 3: Start of call to MSort with Left = 0 and Right = 1 The partially sorted array is: 32 12 Level = 4: Start of call to MSort with Left = 0 and Right = 0 The partially sorted array is: 32 Level = 4: End of call to MSort with Left = 0 and Right = 0 The sorted array is: 32 Level = 4: Start of call to MSort with Left = 1 and Right = 1 The partially sorted array is: 12 Level = 4: End of call to MSort with Left = 1 and Right = 1 The sorted array is: 12 Level = 3: End of call to MSort with Left = 0 and Right = 1 The sorted array is: 12 32 Level = 3: Start of call to MSort with Left = 2 and Right = 3 The partially sorted array is: 34 54 Level = 4: Start of call to MSort with Left = 2 and Right = 2 The partially sorted array is: 34 Level = 4: End of call to MSort with Left = 2 and Right = 2 The sorted array is: 34 Level = 4: Start of call to MSort with Left = 3 and Right = 3 The partially sorted array is: 54 Level = 4: End of call to MSort with Left = 3 and Right = 3 The sorted array is: 54 Level = 3: End of call to MSort with Left = 2 and Right = 3 The sorted array is: 34 54 Level = 2: End of call to MSort with Left = 0 and Right = 3 The sorted array is: 12 32 34 54 Level = 2: Start of call to MSort with Left = 4 and Right = 7 The partially sorted array is: 6 56 76 8 Level = 3: Start of call to MSort with Left = 4 and Right = 5 The partially sorted array is: 6 56 Level = 4: Start of call to MSort with Left = 4 and Right = 4 The partially sorted array is: 6 Level = 4: End of call to MSort with Left = 4 and Right = 4 The sorted array is: 6 Level = 4: Start of call to MSort with Left = 5 and Right = 5 The partially sorted array is: 56 Level = 4: End of call to MSort with Left = 5 and Right = 5 The sorted array is: 56 Level = 3: End of call to MSort with Left = 4 and Right = 5 The sorted array is: 6 56 Level = 3: Start of call to MSort with Left = 6 and Right = 7 The partially sorted array is: 76 8 Level = 4: Start of call to MSort with Left = 6 and Right = 6 The partially sorted array is: 76 Level = 4: End of call to MSort with Left = 6 and Right = 6 The sorted array is: 76 Level = 4: Start of call to MSort with Left = 7 and Right = 7 The partially sorted array is: 8 Level = 4: End of call to MSort with Left = 7 and Right = 7 The sorted array is: 8 Level = 3: End of call to MSort with Left = 6 and Right = 7 The sorted array is: 8 76 Level = 2: End of call to MSort with Left = 4 and Right = 7 The sorted array is: 6 8 56 76 Level = 1: End of call to MSort with Left = 0 and Right = 7 The sorted array is: 6 8 12 32 34 54 56 76 Level 0: main program. The sorted array is: 6 8 12 32 34 54 56 76</PRE> </BODY> </HTML>