Introduction to the

Merge sort is a recursive sort algorithm. The idea is that the array to be sorted is divided into smaller parts until the smaller parts are all sorted arrays (arrays with only one element).

Then combine these sorted arrays in pairs to form a larger array. The larger arrays are then merged until the entire array is sorted.

Example of merge sort

Suppose we have an array: 29,10,14,37,20,25,44,15, how do we merge sort it?

Let’s start with an animation:

Let’s examine the above example in detail:

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

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

[29,10] is divided into two parts [29] and [10], and then merges [29] and [10] to generate [10,29].

Similarly, merge sort is performed on [14,37] to obtain [14,37].

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

Idea of merge sort algorithm

Merge sort mainly uses the idea of divide and conquer. Divide a large array into many, many smaller arrays that have been sorted, and then merge the smaller arrays.

The Divide process can be recursive because the Divide logic is the same whether it is a large array or a small array.

And the logical part of what we’re really doing is merging this piece.

Java implementation of merge sort

Let’s take a look at the core merge section:

   /** * Merges two parts of the sorted array *@paramArray Array * to be merged@paramThe starting point of the first part of the low array *@paramThe end of the first part of the array mid, which is also the start of the second part -1 *@paramThe end of the second part of the high array */
    private void  merge(int[] array, int low, int mid, int high) {
        // The length of the array to sort
        int length = high-low+1;
        // We need an extra array to store the sorted result
        int[] temp= new int[length];
        // Split into left and right arrays
        int left = low, right = mid+1, tempIdx = 0;
        // Merge arrays
        while (left <= mid && right <= high) {
            temp[tempIdx++] = (array[left] <= array[right]) ? array[left++] : array[right++];
        }
        // One array is merged, the remaining one is merged
        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];
    }
Copy the code

Notice that our element is in the original array, and the first argument to the method is the original array.

The next three arguments are the indexes in the array to merge sort. The three indexes divide the array into two parts: array[low to mid], array[mid+1 to high].

The logic of a merge is to merge these two arrays.

Since our array itself is primitive, we need an extra space int[] temp to merge sorts.

By comparing the array [low to mid], array [+ 1 mid to high] elements in size, each element is inserted into the int [] temp, finally will sort the array to copy the original array, after the merge is complete.

Merge then we look at the divide part, which is a recursive call. At the end of the recursive call we merge: merge merge

    public void doMergeSort(int[] array, int low, int high){
        // Array to sort array[low..high]
        // Use dichotomy for recursion. Stop recursion when low is greater than or equal to high
        if (low < high) {
            // Get the intermediate index
            int mid = (low+high) / 2;
            // The first half of the recursion
            doMergeSort(array, low  , mid );
            // The last half of the recursion
            doMergeSort(array, mid+1, high);
            // Merge the two parts of the sorted array
            merge(array, low, mid, high);
            log.info("Array after merge :{}",array); }}Copy the code

Array is the original array, and low and high mark the starting position of the array to recursively sort.

Run the result above:

You can see that the output is consistent with our animation.

Time complexity of merge sort

So let’s see what merge sort does in time.

The merge method actually traverses two arrays, so the time complexity of the merge method is O(N).

Look again at the Divide method:

Divide divides sorting into logN levels. Each level can be viewed as a combined sort of N elements, so the time complexity of each level is O(N).

Add it up, and the total time is order N logN.

The code address of this article:

learn-algorithm

This article has been included in www.flydean.com/algorithm-m…

The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!

Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!