“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!”

preface

Algorithm is the soul of the program, an excellent program can be in the mass of data, still maintain efficient calculation. At present, the interview requirements of major factories are increasingly high, and the algorithm will definitely go. If you don’t want to go to a big factory, you want to go to a small company, you don’t need to ask for an algorithm. But you’ll always be a code worker, just like a brick remover. You’ll probably be out in a year or two. If you don’t want to be a code worker forever, learn data structures and algorithms in your spare time.

912. Sort the array, sort the array itself is not specified to use what sort algorithm, but the interviewer specified the need to use merge sort algorithm to answer, must have his reason.

As we know, there are many sorting algorithms, roughly as follows:

Arrays.sort() in Java uses a sort algorithm named TimSort, which is the optimized version of merge sort. Merge sort has two advantages. First, it has a low average time complexity of O(N*logN). Second, it is stable sorting, that is, the order of equal elements does not change; In addition to these two advantages, the underlying divide-and-conquer idea can be used to solve many of our algorithm problems, which is why the interviewer specifies merge sort. All right, so without further ado, let’s see how merge sort actually works.

Merge sort (recursive version)

Merge-sort is a sorting method based on merging. The algorithm adopts the classic divide-and-conquer strategy, which is divided into two steps: divide and conquer.

1. Divide: first recursively decompose the numbers into subarrays

2. Rule: Merge the subarrays obtained by stages in order

Let’s take a concrete example. Suppose we are given an array: [6,3,2,7,1,3,5,4] and we need to sort it using a merge algorithm, as shown in the following figure:

The stages can be understood as the process of recursively dismantling the molecular sequence, and the recursion depth is log2n. The cure stage is the process of sorting two subsequences. Let’s see how the two arrays [2,3,6,7] and [1,3,4,5] are combined in the last step of the cure stage.

In the figure, the copied temporary array is on the left, and the original array is on the right. We compare the corresponding values of the left and right Pointers, put the smaller number into the original array, and then move the corresponding pointer to the right. For example, in the first step, we compare 2 pointed by L on the left and 1 pointed by R on the right. If 1 pointed by R is small, we put 1 in the first position in the original array, and then R moves to the right. We continue until the elements of the temporary array on the left overwrite the original array on the right. Finally, let’s look at it through the above figure and then combine the source code:

class Solution {
    public int[] sortArray(int[] nums) {
        sort(0, nums.length - 1, nums);
        return nums;
    }

    // point: recursive dichotomy
    private void sort(int l, int r, int[] nums) {
        if (l >= r) return;

        int mid = (l + r) / 2;
        sort(l, mid, nums);
        sort(mid + 1, r, nums);
        merge(l, mid, r, nums);
    }


    // merge nums[mid] and nums[mid+1...r]
    private void merge(int l, int mid, int r, int[] nums) {
        int[] aux = Arrays.copyOfRange(nums, l, r + 1);

        int lp =l, rp = mid + 1;

        for (int i = lp; i <= r; i ++) {
            if (lp > mid) {                // If the left half of the elements have been processed
                nums[i] = aux[rp - l];
                rp ++;
            }  else if (rp > r) {          // If the elements in the right half are all processed
                nums[i] = aux[lp - l];
                lp ++;
            } else if (aux[lp-l] > aux[rp - l]) { // Left half indicates the element > right half indicates the element
                nums[i] = aux[rp - l];
                rp ++;
            } else {                        // The left half indicates the element <= the right half indicates the elementnums[i] = aux[lp - l]; lp ++; }}}}Copy the code

As can be seen, the time complexity of the stages is logN, while that of the merge stage is N, so the time complexity of the merge algorithm is O(N*logN). Because each merge requires arrays within the corresponding range, its space complexity is O(N).

Merge sort (iterative version)

The above merge sort is divided by recursive binary method. In fact, we can also divide the array by iterative method, as shown in the following figure:

Because of the array, we directly merge from 1 through iteration, where Sz is the length of the merge. This method can also be called bottom-up merge, and the specific code is as follows

class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        / / sz = 1,2,4,8... The sorting
        for (int sz = 1; sz < n; sz *= 2) {
            // merge arr[I... I +sz-1] and arr[I +sz... I +2*sz-1]
            for (int i = 0; i < n - sz; i += 2*sz ) {
                merge(i, i + sz - 1, Math.min(i+sz+sz-1, n-1), nums); }}return nums;
    }

  	// Same as the recursive version
    private void merge(int l, int mid, int r, int[] nums) {
        int[] aux = Arrays.copyOfRange(nums, l, r + 1);

        int lp =l, rp = mid + 1;

        for (int i = lp; i <= r; i ++) {
            if (lp > mid) {
                nums[i] = aux[rp - l];
                rp ++;
            }  else if (rp > r) {
                nums[i] = aux[lp - l];
                lp ++;
            } else if (aux[lp-l] > aux[rp - l]) {
                nums[i] = aux[rp - l];
                rp ++;
            } else{ nums[i] = aux[lp - l]; lp ++; }}}}Copy the code

conclusion

Merge sort is a very efficient sorting algorithm whose time complexity is O(N*logN). The best and worst average time complexity of merge sort is O(nlogn), and the order of the elements equal after sorting will not change, so it is also a stable sorting algorithm. Arrays.sort() in Java uses a sort algorithm named TimSort, which is an optimized version of merge sort.