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:

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
#### 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).