### What is merge sort?

A **Divide and Conquer** algorithm that divides the list in two sub-lists and calls itself onto them recursively till it can’t be split and merges them afterwards in a sorted manner.

### Time and Space Complexities

- Best Time Complexity: O(n log(n))
- Average Time Complexity: O(n log(n))
- Worst Time Complexity: O(n log(n))
- Best Space Complexity: O(n)

### Prerequisites

### Steps

- For an array of length ‘N’, split it into two halves(left and right subarrays) as evenly as possible.
- Now, let’s take the left subarray and repeat the step 1 till we have sub arrays of length 1.
- Start to merge the elements of the subarrays in the order they were split with the smallest digit placed at the start.
- Repeat step 3 till the whole left array is sorted and merged.
- Repeat steps 2, 3 and 4 for the right subarray.
- Now take the two sorted subarrays and pick the first elements or both the subarrays, compare them and place the smallest one at the start.
- Repeat step 6 for the proceeding elements.

### Pseudo code

MergeSortedLists(LA, RA, A) { nL = Length of LeftArray (LA) nR = Length of RightArray (RA) i = j = k = 0 while(i<nL and j<nR) { if(LA[i] <= RA[j]) { A[k] = LA[i] i = i+1 } else { A[k] = RA[j] j = j+1 } k = k+1 } while(i<nL) { A[k] = LA[i] i = i+1 k = k+1 } while(j<nR) { A[k] = RA[j] j = j+1 k = k+1 } } MergeSort(A) { n = length of Array (A) if(n<2) return mid = n/2 left = array of size(mid) right = array of size(n-mid) for i = 0 to mid-1 left[i] = A[i] for i = mid to n-1 right[i-mid] = A[i] MergeSort(left) MergeSort(right) Merge(left, right, A) }