Algorithm for Merge Sort with implementation in Java

[16548 views]

Merge sort is one of the most efficient sorting algorithms. Merge sort works on the principle of divide and conquer. Merge sort breaks down an array/list into two halves, then sorts these halves, and finally merges them to form a completely sorted array.

Merge Sort Algorithm:

Find the middle index(q) of Array(A) passed
Divide this array into two parts, p to q and q to r, and call mergeSort function on these two halves
Recursively call step 2 until p < r
Merge these two sorted halves
For merging, create two pointers i&j, one for each half
If left[i] < right[j] then place left[i] into final array and increment i else place right[j] into final array and increment j
If either of i or j reach end of array, copy the other array to final array

There are two major steps to to performed in Merge Sort Algorithm. They are:

Dividing the Array
Merging the Sub-Array

Let's see each of these steps in Detail:

Dividing the Array:

Dividing into sub problems in Merge Sort Algorithm in Java

This array is the one we have to sort via merge sort. mergeSort(A, l, r) divides array A from index l to r into two parts and calls mergeSort() on them recursively until l < r.

if l > r return; q = (l+r)/2; mergeSort(A, l, q); mergeSort(A, q+1, r);

Merging the Sub-problems:

When these two halves are sorted, we need to merge them.

merge(A, l, q, r);

So our final mergeSort() method becomes:

mergeSort(A, l, r) if l > r return q = ( l + r ) / 2 mergeSort( A, l, q ) mergeSort( A, q+1, r) merge(A, l, q, r)

Now we need to write the merge method.

merge(A, l, q, r) leftArray = A[l...q] rightArray = A[q+1 ... r] i,j,k = 0 for i=0 to q, j=q+1 to r if leftArray[i] < rightArray[j] finalArray[k] = leftArray[i] i = i+1 else finalArray[k] = rightArray[j] j = j+1 k++

Merge Sort Algorithm in Java:

public class SortingExample{ static void merge(int arr[], int l, int q, int r){ int leftArraySize = q-l+1; int rightArraySize = r-q; int[] left = new int[leftArraySize]; int[] right = new int[rightArraySize]; for(int idx=0; idx<leftArraySize; idx++) left[idx] = arr[l+idx]; for(int idx=0; idx<rightArraySize; idx++) right[idx] = arr[idx+q+1]; int i,j,k=l; for(i=0, j=0; i<leftArraySize && j<rightArraySize; ){ if(left[i]<=right[j]){ arr[k++] = left[i]; i++; } else{ arr[k++] = right[j]; j++; } } while(i<leftArraySize) arr[k++] = left[i++]; while(j<rightArraySize) arr[k++] = right[j++]; } static void mergeSort(int arr[], int l, int r){ if(l<r){ int q = (l+r)/2; mergeSort(arr, l, q); mergeSort(arr, q+1, r); merge(arr, l, q, r); } } public static void main(String[] args){ int arr[] = {38, 27, 43, 3, 9, 82, 10}; mergeSort(arr, 0, 6); System.out.println("Sorted array"); for(int i=0; i<7; i++) System.out.print(arr[i]+" "); } }

Time Complexity for Merge Sort:

For each instance of array size n, array is divided into two n/2 subarrays.
T(n) = 2T(n/2)
Merging two subarrays take O(n) time. So final equation becomes,
T(n) = 2T(n/2) + O(n)
Solving the above recurrence relation, we get a time complexity of O(nlogn).