> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/merge-sort.md).

# Merge sort

## 1.Merge sort

* This follow divide and conquer approach to create smaller sub-problems
  * A list is broken down into smaller and smaller parts recursively
*  Then merge the sorted lists together to get the fully sorted list

## 2.Divide and Conquer

* A classic recursion based algorithm, divide till the problem is so small as to be trivial
  * Solve for the trivial case and then build up the complete solution as recursion unwinds

## 3.Code

1. The "split" method to split the list into 2 sub-lists
2. The "merge" method to merge 2 sorted lists into sorted list
3. The "mergeSort" method which does the final recursive sort

* Split method (take Θ (n1 + n2) = Θ (n) time )
  * The two lists for the first and second halves have been setup and split simply copies the elements from the first list over
  * The first half holds everything up to the mid-point
  * The second half holds reminder of the elements

```
public static void split(int[] listSort, int[] listFirstHalf, int[] listSecondHalf) {
    int index = 0;
    int secondHalfStrartIndex = listFirstHalf.length;
    for (int element: listToSort) {
        if ( inex < secondHalfStrartIndex) {
            listFirstHalf[index] = listSort[index];
        } else {
            listSecondHalf[index - secondHalfStrartIndex] = listSort[index];
        }
        index++;
    }
}
```

* Merge method (take Θ (n) time )
  * Set up indices into the final merged list and the two halves which are to be merged together.
  * Compare the element at the current index of each of the lists and choose the smaller one to go into the final list
  * Copy over the remaining elements left in either one of the lists

```
public static void merge(int[] listSort, int[] listFirstHalf, int[] listSecondHalf) {
    int mergeIndex = 0;
    int firstHalfIndex = 0;
    int secondHalfIndex = 0;
    
    while (firstHalfIndex < listFirstHalf.length &&
           secondHalfIndex < listSecondHalf.length){
           if (listFirstHalf[firstHalfIndex] < listSecondHalf[secondHalfIndex]) {
                  listSort[mergeIndex] = listFirstHalf[firstHalfIndex];
                  firstHalfIndex++;
           } else if (secondHalfIndex < listSecondHalf.length) {
                  listSort[mergeIndex] = listFirstHalf[secondHalfIndex];
                  secondHalfIndex++;
           }
           mergeIndex++;
    }
    
    if (firstHalfIndex < listFirstHalf.length) {
           while (mergeIndex < listToSort.length) {
                  listSort[mergeIndex] = listFirstHalf[firstHalfIndex++];
           }
    }
   
    if (secondHalfIndex < listSecondHalf.length) {
           while (mergeIndex < listToSort.length) {
                  listSort[mergeIndex] = listFirstHalf[secondHalfIndex++];
           }
    }
}
```

* MergeSort

```
public static void mergeSort(int[] listSort) {
    //A list of length 1 is a sorted list! 
    //This is the base case of recursion
    if (listSort.length == 1) {
        return;
    }
    
    //Get the mid-point at which to split the list
    int midIndex = listSort.length/2 + listSort.length%2;
    int[] listFirstHalf = new int[midIndex];
    int[] listSecondHalf = new int[listSort.length - midIndex];
    split(listSort, listFirstHalf, listSecondHalf);
    
    //Recursive call, merge sort the two smaller sub-lists created
    mergeSort(listFirstHalf);
    mergeSort(listSecondHalf);
    
    //Merge the sorted list to get the original list in sorted order
    merge(listSort, listFirstHalf, listSecondHalf);
    print(listSort);
}
```

## **4.Complexity**

* The complexity of Merge sort is O(NLogN)&#x20;
* The algorithm is not adaptive
* It takes O(N) extra space when we use arrays (all the smaller lists we create in the divide phase)
* It is a stable sort
* Running time T(n) of merge sort:

```
T(n) = 
Θ(1)       if n = 1
2T(n/2) + Θ(n)    if n > 1
```