Look at animation algorithms: sorting merging sorting

catalogue

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 start with an animation:

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 [29] and [10], and then [29] and [10] 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).

Code address of this article:

learn-algorithm

This article has been included in http://www.flydean.com/algorithm-merge-sort/

The most popular interpretation, the most profound dry goods, the most concise tutorials, and many tips you don't know are waiting for you to find!

Welcome to my official account: "procedures and things". I understand technology and you better!

Tags: Algorithm data structure Permutation

Posted by Tea_J on Mon, 30 May 2022 08:05:47 +0530