# Algorithm for Merge Sort in Java

(3140 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:

1. Find the middle index(q) of Array(A) passed
2. Divide this array into two parts, p to q and q to r, and call mergeSort function on these two halves
3. Recursively call step 2 until p < r
4. Merge these two sorted halves
5. For merging, create two pointers i&j, one for each half
6. 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
7. 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:

1. Dividing the Array
2. Merging the Sub-Array
Let's see each of these steps in Detail:

#### Dividing the Array: 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 O(nlogn).