Merge and Radix Sort

Divide and Conquer

Divide and Conquer is an algorithm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

Divide the problem into a number of sub-problems

Conquerthe sub-problems

• Solve the sub-problems recursively
• Sub-problem size small enough => solve the problems in straight forward manner

Combine the solutions of the sub-problems

• Obtain the solution for the original problem

Merge Sort

Merge Sort is a classical sequential sorting algorithm using divide and conquer approach. The unsorted list is first divided into half. Each half is again divided into two. It is continued until individual numbers are obtained. Then pairs of numbers are combined (merged) into sorted list of two numbers. Pairs of these lists of four numbers are merged into sorted lists of eight numbers. This is continued until the one fully sorted list is obtained.

Merge Sort on an input sequence S with n elements consists of three steps:

• Divide: partition S into two sequences S1 and S2 of about n/2 elements each
• Recur: recursively sort S1 and S2
• Conquer: merge S1 and S2 into a unique sorted sequence

Algorithm: MergeSort(A,left,right)

Input: A is an unsorted array, left is the beginning index and right is the last index, A[left right]

Output: A[left ... right]sorted array.

if left < right then

mid = [ (left+right)/2 ]

MergeSort(A, left, mid)

MergeSort(A, mid+1, right)

MergeSort(A, left, mid, right)

where MergeSort(A, p, q, r) is given as:

MergeSort(A,p,q,r)

n1 = q - p + 1

n2 = r - q

let L[1..n1+1] and R[1..n2+1] be new arrays

for i=1 to n1

L[i] = A[p+i-1]

for j = 1 to n2

R[j] = A[q+j]

L[n1+1] = inf

R[n2+1] = inf

i = 1

j = 1

for k = p to r

if L[i] <= R[j]

A[k] = L[i]

i = i + 1

else

A[k] = R[j]

j = j + 1

Analysis of Merge Sort:

n = length of array

Divide step = O(1)

Conquer step = 2T(n/2)

Combine time = O(n)

Fig: Time analysis of Merge Sort

T(n) = 2 * T(n/2) + n

= 2 * (2 * T(n/4) +n/2) + n

= 4 * T(n/4) + 2n

= 4 * (2 * T(n/8) + n/4) + 2n

= 8 * T(n/8) + 3n

. . .

= 2^k* T(n/2^k) + kn

Here, n = 2^k, so k = log₂n

So, T(n) = n + nlog₂n

i.e. T(n) = O(nlog₂n)

Example: Sorting 7,2,9,4,3,8,6,1

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Step 8

Step 9

Step 10

Radix Sort

Origin: Herman Hollerith's card-sorting machine for the 1890 U.S. Census.

Radix Sort involves digit-by-digit sort. It is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. Because integers can represent strings of characters and specially formatted floating point numbers, radix sort is not limited to integers.

Algorithm: RadixSort(A,n,d,k,j)

where A = input array, n = array size, d = # of digits, k = the digit being sorted, j = array index

for 0 <= p <= 9

do Q[p] = empty queue

D = 1

for 1 <= k <= d

do

d = 10 *D

for 0 <= i < n

do t = (A[i] mod D) div (d/10)

enqueue(A[i], Q[t]);

j = 0;

for 0 <= p <= 9

do while Q[p] is not empty

A[j] = dequeue(Q[p])

j = j + 1

Example: 275, 087, 426, 061, 509, 170, 677, 503

Thus, the array of integers is sorted.

References:

1.https://en.wikipedia.org/wiki/Radix_sort

2.https://en.wikipedia.org/wiki/Merge_sort

3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”

4. G. Brassard and P. Bratley, “Fundamentals of Algorithms”