# 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/merge-sort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.