Merge sort

Merge sort is a more efficient sorting algorithm than either selection sort or bubblesort.

Where bubble sort and selection sort are O(n²), merge sort is O(n.log n).

The basic idea is that if you know you have two sorted lists, you can combine them into a single large sorted list by just looking at the first item in each list. Whichever is smaller is moved to the single list being assembled. There is then a new first item in the list from which the item was moved, and the process repeats.

The process overall is thus:

1. Split the original list into two halves
2. sort each half (using merge sort)
3. merge the two sorted halves together into a single sorted list

Example

Algorithm

	procedure mergesort(first,last,array)
		mid= (first+last)/2
		mergesort(first,mid,array)
		mergesort(mid+1,last,array)
		rejoin_two_halves(mid,array)
	end mergesort

Code

procedure main is

type int_array is array(1..100) of integer;
tosort:int_array;

    procedure merge (a:in out int_array; low,mid,high:in integer) is
       temp: int_array;
       choose1: boolean;
       loop_low,loop_high:integer;

    begin
       loop_low:=low;
       loop_high:=high;

       for i in low..high loop

          if (loop_low>mid) then choose1:=false;
          elsif (loop_high>high) then choose1:=true;
          else  choose1:= a(loop_low)<a(loop_high);
          end if;			-- choose which side

          if choose1 then		-- choose from low side
              temp(i):=a(loop_low);
              loop_low:=loop_low+1;
          else
              temp(i):=a(loop_high);	-- choose from high side
              loop_high:=loop_high+1;
          end if;
       end loop;
       a:=temp;
    end merge;

    procedure mergesort(a: in out int_array;low,high:integer) is
       mid:integer;
    begin
       if low<high then
         mid:= (high+low)/2;
         mergesort(a,low,mid);
         mergesort(a,mid+1,high);
         merge(a,low,mid,high);
       end if;
    end mergesort;

begin
	-- something happens here to get the initial values of tosort

	-- then use mergesort to sort the array
	mergesort(tosort,1,100);

end main;