# brief introduction

Merge sort for short is a sort algorithm based on recursion. The idea of this algorithm is to divide the array to be sorted into many small parts until these small parts are sorted arrays (arrays with only one element).

These sorted arrays are then combined in pairs to form a larger array. Then continue to merge these larger merged arrays until the entire array is sorted.

# Examples of merge sort

If we have an array: 29,10,14,37,20,25,44,15, how can we merge and sort it? Let's analyze the operation process of the above example in detail:

First, divide the array into two parts, [29,10,14,37] and [20,25,44,15].

[29,10,14,37] is divided into two parts [29,10] and [14,37].

[29,10] is divided into two parts  and , and then  and  are merged and sorted to generate [10,29].

Similarly, merge and sort [14,37] to get [14,37].

Merge and sort [10,29] and [14,37] again to get [10,14,29,37], and so on to get the final result.

# Idea of merging sorting algorithm

Merge sort mainly uses the idea of divide and rule. Divide a large array into many, many sorted small arrays, and then merge the small arrays.

This divide process can use recursive algorithm, because the divide logic is the same whether it is a large array or a small array.

The logical part of sorting is to merge this block.

# java implementation of merge sort

Let's take a look at the core of the merge:

```   /**
*Merge two sorted arrays
* @param array Array to be merged
* @param low   Starting point of the first part of the array
* @param mid   The end of the first part of the array and the start of the second part -1
* @param high  End of second part of array
*/
private void  merge(int[] array, int low, int mid, int high) {
// Length of array to sort
int length = high-low+1;
// We need an extra array to store the sorted results
int[] temp= new int[length];
//Split into left and right arrays
int left = low, right = mid+1, tempIdx = 0;
//Merge array
while (left <= mid && right <= high) {
temp[tempIdx++] = (array[left] <= array[right]) ? array[left++] : array[right++];
}
//One array is merged, and the remaining one continues to merge
while (left <= mid) temp[tempIdx++] = array[left++];
while (right <= high) temp[tempIdx++] = array[right++];
//Copy the sorted array back to the original array
for (int k = 0; k < length; k++) array[low+k] = temp[k];
}
```

You should note that our elements are stored in the original array, and the first parameter of the method is the original array.

The last three parameters are the index in the array that needs to be merged and sorted. The three indexes divide the array into two parts: array[low to mid], array[mid+1 to high].

The logic of merge is to merge these two arrays.

Because our array itself stores the original, in order to merge and sort, we need to use an additional array space int[] temp.

By comparing the size of the elements in array[low to mid], array[mid+1 to high], insert the elements into int[] temp one by one, and finally copy the sorted array back to the original array. merge is completed.

Then let's take a look at the divide part. The divide part is actually a recursive call. At the end of recursion, we need to call the merge method:

```    public void doMergeSort(int[] array, int low, int high){
// Array to sort array[low..high]
//Use dichotomy to recurse. When the value of low is greater than or equal to the value of high, stop recursion
if (low < high) {
//Get index of intermediate value
int mid = (low+high) / 2;
//Recursive first half
doMergeSort(array, low  , mid );
//The second half of recursion
doMergeSort(array, mid+1, high);
//After recursion, merge the two parts of the sorted array
merge(array, low, mid, high);
log.info("merge Array after:{}",array);
}
}
```

Array is the original array. low and high mark the starting position of the array to be sorted recursively.

Run the above results: It can be seen that the output results are consistent with those shown in our animation.

# Time complexity of merge sort

Let's look at the time complexity of merge sort.

First, let's look at the merge method. The merge method actually traverses two arrays, so the time complexity of the merge method is O(N).

Take another look at the divide method: The divide method divides sorting into logN layers. Each layer can be regarded as a combined sorting of N elements. Therefore, the time complexity of each layer is O(N).

Taken together, the total time complexity is O(N logN). 