MERGESORT

MERGE
		-array  		(sentinel value at the end in each case)
		-linked list	


MERGESORT 

Sort first half, sort second half, merge  

Ex 

LIST_A	7	9	3	1	4	|	2	8	6	2	0

Sort each half of the list separately.

LIST_A	1	3	4	7	9	|	0	2	2	6	8

Copy the list into a new list, LIST_B, where the second half of the list is copied in reverse order.

LIST_B	1	3	4	7	9	|	8	6	2	2	0

Merge the two halfs of LIST_B into LIST_A. Because of the way LIST_B is set up, no sentinel values are required. 

LIST_A	0	1	2	2	3	4	6	7	8	9


LIST  MERGE  SORT (linked list implementation)

	{Split the list in half}

		C-pointer to the beginning of the list 
		B:=C:next
		while  B<>z	do begin
			C:= C^.NEXT;
			B:=B^.NEXT;	B:=B^NEXT
		end;

	{C halts at the middle of the list}

	B :=C^.NEXT;	{Beginning of second half}

	C^.NEXT := Z;	{Sentinel value., for 1st half}



BOTTOM-UP (non-recursive)   MERGESORT 

Merge consecutive elements (considered as sorted sublists of size 1), then consecutive pairs, then consecutive sublists of order 4, etc., until the list is sorted. 

Ex 

7	9	3	1	4	2	8	6	2	0

Pass 1 

Consider each element as a sorted sublist. Merge consecutive pairs of elements to get sorted sublists of size 2. 

7	9	|	3	1	|	4	2	|	8	6	|2	0

Pass 1 complete 

Pass 2 

Merge consecutive sorted sublists of size 2 to get sorted sublists of size 4 or less. 

1	3	7	9	|	2	4	6	8	|	0	2

Pass 2 complete 

Pass 3 

Merge consecutive pairs of sorted sublists. 

1	2	3	4	6	7	8	9	|	0	2

Pass 3 complete 

Pass 4 

Merge consecutive sublists. 

0	1	2	2	3	4	6	7	8	9

Pass 4 complete 


Proposition 	 MERGESORT uses about N lg N comparisons.              .

Proof Non-Recursive version
When merging two lists of size M1 and M2, there are about M1 + M2 comparisons, and there are about lg N passes. 
Recursive version If M(N) is the number of comparisons which MERGESORT makes for a list of size N, then M(N)=2 M(N/2)  + N,  M(1)=0, then M(N) is about N lg N by the results on recurrence relations. 


Proposition MERGESORT uses extra space proportional to N.
		MERGESORT is stable.
		MERGESORT is insensitive to input. (There is no worst case.)

RECURSION REVISITED

MERGESORT is "DIVIDE & CONQUER" while QUICKSORT is  "CONQUER & DIVIDE"

We can optimize MERGESORT by handling small subfiles differently.