Merge sort is that simple

From the front has explained bubble sort, select sort, insert sort, quick sort, this chapter mainly explains merge sort, hope you can understand and handwritten merge sort quick sort code, and then pass the interview! Please point out in the comments if I have made any mistakes.

Introduction to merge sort

Source BCO:

Merge-sort is an effective sorting algorithm based on MERGE operation. It is a typical application of Divide and Conquer. The ordered subsequences are combined to obtain a fully ordered sequence. That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are merged into one ordered table, it is called binary merge.

Process Description:

The merging process is as follows: compare the size of a[I] and b[j], if a[I]≤b[j], copy the element a[I] in the first ordered table into r[k], and add 1 to I and k respectively; Otherwise copy the element b[j] from the second ordered table into r[k], add j and k to 1, and so on until one of the ordered tables is finished, and then copy the remaining elements from the other ordered table into the element from subscripts k to t in R. The algorithm of merge sort is usually achieved by recursion. First, the interval [S,t] to be sorted is divided by the midpoint, then the left sub-interval is sorted, and then the right sub-interval is sorted, and finally the left and right intervals are merged into the ordered interval [s,t] by a merge operation.

Principle:

Merge operations work as follows:

The first step is to apply for a space equal to the sum of the two sorted sequences. This space is used to store the combined sequence

Step 2: Set two Pointers, starting at the start of two sorted sequences

Step 3: Compare the two Pointers to the element, select the smaller element into the merge space, and move the pointer to the next position

Repeat step 3 until a pointer exceeds the end of the sequence

Copies all remaining elements of the other sequence directly to the end of the merged sequence

Here’s a quick summary:

• Merging two sorted arrays into one ordered array is called merge sort
• Step: Iterate over two arrays, comparing their values. Whoever is smaller gets put in the larger array first until the array is traversed

First, calculate the merge sort process

Now I have two sorted arrays: int[] arr1 = {2, 7, 8} and int[] arr2 = {1, 4, 9}, and I have a large array to load them int[] arr = new int[6];

1.1

So, I compare the values of the two arrays, and whoever has the smaller value goes in the larger array!

First, compare arr1[0] with ARR2 [0]. Obviously, ARR2 [0] is small, so put ARR2 [0] in the large array, and at the same time, arR2 pointer is one latter

So, arr = {1} so far

1.2

Then, compare arr1[0] with ARR2 [1], obviously arr1[0] is smaller, put ARR1 [0] into the large array, and at the same time, arR1 pointer is one latter

So, arr = {1,2} so far

1.3

Then, compare arR1 [1] with ARR2 [1]. Obviously, ARR2 [1] is smaller, put ARR2 [1] into the large array, and at the same time, the arR2 pointer is one latter

So, arr = {1,2,4} so far

.

At the end of the loop, we turn two sorted arrays into one sorted array arr = {1,2,4,7,8,9}

Ii. Merge Sort premise Analysis (Divide-and-conquer method)

From the above calculation we know that the premise of merge sort is to need two sorted arrays, there are usually not two sorted arrays for us **(usually a disorderly array)**, so this algorithm is not very weak??

Int [] arr = {2, 7, 8, 1, 4, 9};

So when we do merge we split it at arr[3] where the element is one. We then use a pointer L to arr[0], a pointer M to arr[3], and a pointer R to arr[5](the last bit of the array). With Pointers, we can split the array into two ordered arrays.

However, as mentioned above, it is usually given a random array, which is still not up to the requirements. Int [] arrays = {9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8};

This is where the idea of divide-and-conquer comes in:

• So we can think about it the same wayint[] arr = {2, 7, 8, 1, 4, 9};The array is divided into parts,arr[0]It’s an ordered array,arr[1]It is also an ordered “array” with Pointers (L,M,R)likeSort both arrays the same way. The final synthesis{2, 7}. againKeep breaking up and mergingAnd finally back to ours,2,4,7,8,9 arr = {1}, soMerge sort can sort messy arrays

This is our divide-and-conquer method, where we take a big problem and break it up into many smaller problems and then put them back together again

Three, merge code implementation

Implementation steps:

1. Break up
2. merge

.

    public static void main(String[] args) {
        int[] arrays = {9.2.5.1.3.2.9.5.2.1.8};
        mergeSort(arrays, 0, arrays.length - 1);

        System.out.println("Public account: Java3y" + arrays);


    }

    /** * merge sort **@param arrays
     * @paramL refers to the first element of the array *@paramR refers to the last element of the array */
    public static void mergeSort(int[] arrays, int L, int R) {

        // If there is only one element, there is no need to sort
        if (L == R) {
            return;
        } else {

            // Take the middle number and split it
            int M = (L + R) / 2;

            // The number on the left keeps splitting
            mergeSort(arrays, L, M);

            // The number on the right keeps splitting
            mergeSort(arrays, M + 1, R);

            / / merge
            merge(arrays, L, M + 1, R); }}/** * merge array **@param arrays
     * @paramL refers to the first element of the array *@paramM refers to the array delimited element *@paramR refers to the last element of the array */
    public static void merge(int[] arrays, int L, int M, int R) {

        // The size of the left array
        int[] leftArray = new int[M - L];

        // The size of the array on the right
        int[] rightArray = new int[R - M + 1];

        // Populate the two arrays with data
        for (int i = L; i < M; i++) {
            leftArray[i - L] = arrays[i];
        }
        for (int i = M; i <= R; i++) {
            rightArray[i - M] = arrays[i];
        }


        int i = 0, j = 0;
        // The first element of the array
        int  k = L;


        // Compare the values of the two arrays, and place the smaller one on the array
        while (i < leftArray.length && j < rightArray.length) {

            // Who is smaller, who puts the element in the large array, moves the pointer, and continues to compare the next one
            if (leftArray[i] < rightArray[j]) {
                arrays[k] = leftArray[i];

                i++;
                k++;
            } else{ arrays[k] = rightArray[j]; j++; k++; }}// If the left array has not been compared and the right array has been compared, copy the left array into the large array (the rest are large numbers).
        while (i < leftArray.length) {
            arrays[k] = leftArray[i];

            i++;
            k++;
        }
        // If the array on the right has not been compared, then copy the number on the right into the larger array (the rest are large numbers).
        while(j < rightArray.length) { arrays[k] = rightArray[j]; k++; j++; }}Copy the code

When I debug it for the first time, it’s easier to understand:

• Split the first two pieces of a large array and load them as an array

• The smaller elements of the smaller array are put into the larger array first

The above two steps continue in a loop, resulting in an ordered array:

Fourth, merge sort optimization

Source: www.cnblogs.com/noKing/p/79…

Here are the main points, and those who are interested can go to the link above:

• When the recursion is small enough, insertion sort is used
• Let’s see if we still need to merge before we merge
• Make space only once before sorting

If the article has the wrong place welcome to correct, everybody exchanges with each other. Students who are used to reading technical articles on wechat and want to get more Java resources can follow the wechat public account :Java3y