C For Swimmers : Mastering C step-by-step

Merge Sort

Definition : 

Merge-sort is based on the divide-and-conquer paradigm. The Merge-sort algorithm can be described in general terms as consisting of the following three steps:

1. Divide Step 
If given array A has zero or one element, return S; it is already sorted. Otherwise, divide A into two arrays, A1 and A2, each containing about half of the elements of A. 

2. Recursion Step 
Recursively sort array A1 and A2. 

3. Conquer Step 
Combine the elements back in A by merging the sorted arrays A1 and A2 into a sorted sequence. 

i = j1
A₁[m+1], A₂[n+1] = INT_MAX
For k = 1 to m + n do
    if A₁[i] < A₂[j]
        then A[k] = A₁[i]
            i = i +1
        else
            A[k] = A₂[j]
                j = j + 1

The Merge sort algorithm is as follows:

MERGE_SORT (A)

A₁[1 . . floor(n/2)] = A[1 . . floor(n/2)]
A₂[1 . . floor(n/2)] = A[1 + floor(n/2) . . n]
Merge Sort (A₁)
Merge Sort (A₁)
Merge Sort (A₁, A₂, A)

FREE Source Code

Click Here: Merge Sort - Ascending Order

• Merge Sort (Breadth First, Input List size is a power of 2)

• Merge Sort (Breadth First, with User Input, Input List size must be a power of 2)

• Merge Sort (Depth First, Input List size is not a power of 2)

• Merge Sort (Depth First, with User Input, Input List size may not be a power of 2)