To implement merge sort in JAVA

By Sukriti Sinha

In this blog, we will discuss the idea of implementing merge sort in JAVA with the help of algorithm and code.

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