To implement merge sort in JAVA

Input: We are given an array or sequence of n numbers (a₁, a₂ … a_n).

Output: A permutation (reordering) of the given sequence such that they are arranged in ascending order.

The basic idea behind insertion sort is that we use the divide and conquer approach. We divide the array into smaller subarrays, sort them and finally merge them.

Algorithm:

The Divide Step:

MergeSort(A, p, r)

                                If p > r

                                                Return

                                q = (p + r)/2

                                MergeSort(A, p, q)

                                MergeSort(A, q+1, r)

The merge step:

Merge(A, p, q, r)

n₁ = q – p +1

n₂ = r – q

let L[1 … n₁ +1] and R[1 … n₂ + 1] be new arrays

for i = 1 to n₁

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

for j = 1 to n₂

                R[j] = A[q +j]

L[n₁ + 1] = ∞

R[n₂ + 1] = ∞

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