# Monthly Archives: December 2011

## 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〉. Posted by on December 5, 2011 in Algorithms

## 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)

Posted by on December 5, 2011 in Algorithms

## 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.

• Increase the speed.

By running sub problems in parallel.

• Increase the Cache Performance.

Applications

More work on divide phase.
Less work for others.

Less work on divide phase.
More work for others.