Merge Sort

The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively, it operates as follows.
Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.
Conquer: Sort the two subsequences recursively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.

Merge sort procedure
Input : A an array in the range 1 to n.
Output : Sorted array A.

Procedure MERGESORT (A,l,r)
1.   if l < r
2.    	then q ← (l+r )/2 
3.    		MERGESORT (A,l,q)
4.  		MERGESORT (A,q+1, r)
5.  		MERGE (A,l,q,r)

Merge procedure (Algorithm 1)

Procedure MERGE (A,l,q,r)
1.  i ← l
2.  j ← q+1
3.  k ← 0
4.  while (i ≤ q) and ( j ≤ r) do
5.   	 k  ← k+1
6.  	 if A[i] ≤ A[j] then
7.  		 TEMP [k] ← A [i]
8.  		 i ← i +1
9.  	 else
10.  		 TEMP [k] ← A [j]
11.  		 j ← j +1
12. if j > r  then 
13.   	 for t ←0 to q – i do
14. 		 A [r-t] ← A [q-t]
15.  for t ← 0 to k-1 do
16. 	 A [l +t] ← TEMP [t+1]

Merge procedure (Algorithm 2)

MERGE(A, p, q, r)
	1 	n1 ← q - p + 1 
	2 	n2 ← r - q 
	3	 create arrays L[1.. n1 + 1] and R[1.. n2 + 1] 
	4 	for i ← 1 to n1
 	5 		do L[i] ← A[p + i - 1]
 	6	 for j ← 1 to n2 
	7 		do R[j] ← A[q + j] 
	8 	L[n1 + 1] ← ∞ 
	9 	R[n2 + 1] ← ∞ 
	10 	i ← 1 
	11 	j ← 1 
	12 	for k ← p to r 
	13		 do if L[i] ≤ R[j] 
	14 			then A[k] ← L[i] 
	15		 	i ← i + 1 
	16 			else A[k] ← R[j] 
	17				 j ← j + 1

Analysis of Merge Sort
To find the middle of the sub array will take D(n)=(1).
To recursively solve each sub problem will take 2T(n/2).
To combine sub arrays will take (n).

Therefore T(n)=T(n/2)+ (n) + (1)
We can ignore (1) term.

The operation of merge sort on the array A = 〈5, 2, 4, 7, 1, 3, 2, 6〉.

QuickSort Algorithm

Left
Middle(only one element)
Right

Procedure QUICKSORT (A,p,r)
 1 if p < r
 2     then q ← PARTITION(A,p,r)
 3             QUICKSORT (A,p,q-1)
 4             QUICKSORT (A,q+1,r)

Partition Algorithm 01

Procedure PARTITION(A,p,r)
1    x ←  A[p]
2    i ←  p -1
3    j ← r +1 
4    while  TRUE
5           do repeat  j ←  j  - 1
6                    until  A[j]   ≤ x 
7                 repeat   i  ←  i + 1  
8                    until   A[i] ≥ x
9                 if    i < j	
10                    then   exchange A[i] ↔A[j]
11                   else return j

Partition Algorithm 02

PARTITION(A, p, r) 

1 x ← A[r] 
2 i ← p - 1 
3       for j ← p to r - 1 
4           do if A[j] ≤ x 
5                    then i ← i + 1 
6                      exchange A[i] ↔ A[j] 
7      exchange A[i + 1] ↔ A[r] 
8   return i + 1

Analysis of Quick sort
The running time of quick sort depends on the partitioning of the sub arrays:
(a) Worst case partitioning(Unbalanced)



 

nOccurs when the sub arrays are completely unbalanced.

nHave 0 elements in one sub array and n − 1 elements in the other sub array.

nTime taken for partitioning is  Q(n) and T(0)= Q(1).

 

nTherefore Recurrence Equation is

T(n) = T(n-1) +T(0)+ Q(n)

Divide and Conquer Method

Divide: Break the problem into subproblems recursively.

Conquer: Solve each sub problems.

Combine: All the solutions of sub problems are combined to get the solution of the original problem.

Advantages

• Increase the speed.

By running sub problems in parallel.

• Increase the Cache Performance.

Applications

• Quick Sort

More work on divide phase.
Less work for others.

• Merge Sort

Less work on divide phase.
More work for others.