A22.0002 - ASSIGNMENT 7


One of the algorithms used to sort an array of data is called Merge Sort. This is a recursive algorithm:

  1. The array is split in half.
  2. Call the sorting algorithm passing the lower half of the array.
  3. Call the sorting algorithm passing the upper half of the array.
  4. Merge the two halfs preserving the correct order.
The recursion stops when the list has only one element.

Example of the algorithm in action using the array [4 6 3 2 1 7]:

   Sort [4 6 3 2 1 7]
      Sort [4 6 3]
         Sort [4]
         Sort [6 3]
	    Sort [6]
	    Sort [3]
	    Merge [6] & [3] ==> [3 6]
	 Merge [4] & [3 6]  ==> [3 4 6]
      Sort [2 1 7]
         Sort [2]
	 Sort [1 7]
	    Sort [1]
	    Sort [7]
	    Merge [1] & [7]  ==> [1 7]
	 Merge [2] & [1 7] ==> [1 2 7]
      Merge [3 4 6] & [1 2 7] ==> [1 2 3 4 6 7]
The program is as follows:
   PROGRAM MergeSort;
   
   CONST DATASIZE = 25;
      
   TYPE dataArr = array [1..DATASIZE] of integer;
      
   PROCEDURE Merge(orig : dataArr; lowStr, lowEnd, highStr, highEnd : integer; VAR new : dataArr);
   
   { Merge the two parts of the array }

   { orig    : the original array }
   { lowStr  : start of lower half }
   { lowEnd  : end of lower half }
   { highStr : start of upper half }
   { highEnd : end of upper half }
   { new     : the new merged array }
   
   VAR index, midPoint : integer;
      
   BEGIN
   END; { Merge }
   
   PROCEDURE Sort(VAR data	: dataArr; start, finish : integer);
   
   { Sort the array using recursion }

   { data   - the array to be sorted }
   { start  - where to start sorting }
   { finish - where to stop sorting }
   
   VAR numElements, midPoint : integer;
      index		  : integer;
      
   BEGIN
    
      numElements := finish - start + 1;
      
      { If only one element, nothing to do else use recursion }
      
      IF numElements > 1 THEN
      BEGIN
         midPoint := start + numElements DIV 2 - 1;
         Sort(data, start, midPoint);
         Sort(data, midPoint+1, finish);
         Merge(data, start, midPoint, midPoint+1, finish, data);
      END;
   END; { Sort }
   
   VAR data	      : dataArr;
      index, numElements : integer;
   
   BEGIN
      index := 1;
      writeln('Enter up to ', DATASIZE, ' integers to be sorted.');
      WHILE (NOT EOLN) AND (index <= DATASIZE) DO
      BEGIN
         read(data[index]);
         index := index + 1;
      END;
   
      numElements := index - 1;
      
      Sort(data, 1, numElements);
   
      writeln;
     
      FOR index := 1 TO numElements DO
         write(data[index],' ');
   
      writeln;
   END.

You assignment is to write the Merge procedure.

You can dowload the above source code here.