The less a man needs, the greater is his happiness, and the more he desires, the less is his freedom. — Gorky, My University

This is the 11th day of my participation in Gwen Challenge

First, algorithm thought

Merge sort is one of the most popular sorting algorithms, which is based on the principle of divide-and-conquer algorithm. Here, a problem is divided into subproblems. Each subproblem is solved individually. Finally, subproblems are combined to form a final solution.

As shown in the figure below, the merge sort algorithm recursively splits the array in half until we reach the case of an array with one element. After that, the merge function takes the sorted subarrays and merges them to gradually sort the entire array.

1. The illustration

Suppose we try to sort the elements in ascending order.

Second, the work process

Merge sort is based on the idea of divide and conquer, broken down into two steps:

Partition: To recursively divide an array into subarrays of one element, each of which is already sorted

Governance: Combine sorted subarrays according to rules to build a final sorted array

The most important step in the merge sort algorithm is the merge step, which is the solution of combining two sorted subarrays to build a large sorted array.

The steps for writing merge functions

Assuming the original array is arr[p..r] (p is the first index, r is the last index) and q is the intermediate point between p and R, we can split the original array arr[p..q] and arr[q+1..r] into two subarrays arr[p..q] and arr[q+1..r].

The task of the merge function is to merge two subarrays arr[p..q] and arr[q+1..r] to create a sorted array arr[p..r], so the input of the function is arr, p, q, and r

Steps for writing merge functions:

1. Create two subarrays, respectivelyArr [P.. Q] -> L and ARR [Q +1.. R] -> M
2. Put the elements of the original array into two subarrays
3. Create three Pointers I, j, k
   • I points to the index of the first subarray L, starting at 0
   • J points to the index of the second subarray M, starting at 0
   • K points to the index of the original array, starting with p
4. Iterate over two subarrays, selecting the smaller elements and placing them in the correct place in the original array until you reach the end of either subarray
5. Place the remaining elements of the subarray at the end of the original array

The code implementation is as follows:

// Merge the subarray elements into the original array
void merge(int arr[], int p, int q, int r) {

    // Create two subarrays L ← A[p..q] and M ← A[q+1..r]
    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1], M[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[p + i];
    for (int j = 0; j < n2; j++)
        M[j] = arr[q + 1 + j];

    // Define a pointer to the current index position of the subarray and the original array
    int i, j, k;
    i = 0;
    j = 0;
    k = p;


    // Iterate over the two subarrays, select the smaller elements and place them in the correct positions in the original array,
    // until the end of any subarray is reached
    while (i < n1 && j < n2) {
        if (L[i] <= M[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = M[j];
            j++;
        }
        k++;
    }

    // Place the remaining elements of the subarray at the end of the original array
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while(j < n2) { arr[k] = M[j]; j++; k++; }}Copy the code

The Merge() function is explained step-by-step

There’s a lot going on with this function, so let’s take an example to see how it works.

A picture is worth a thousand words. Suppose the original array is as follows:

The array A[0..5] contains two sorted subarrays A[0..3] and A[4..5]. Let’s see how the merge function merges two arrays.

Step 1: Create a duplicate copy of the subarray to sort

// Create L ← A[p..q] and M ← A[q+1..r]
int n1 = q - p + 1 = 3 - 0 + 1 = 4;
int n2 = r - q = 5 - 3 = 2;

int L[4], M[2];

for (int i = 0; i < 4; i++)
    L[i] = arr[p + i];
// L[0,1,2,3] = A[0,1,2,3] = [1,5,10,12]

for (int j = 0; j < 2; j++)
    M[j] = arr[q + 1 + j];
// M[0,1] = A[4,5] = [6,9]
Copy the code

Step 2: Maintain the current index of the subarray and the main array

    
    int i, j, k;
    i = 0; 
    j = 0; 
    k = p; 
Copy the code

Step 3: Until we reach the end of L or M, select the smaller elements in L and M and place them in A[p… R]

    while (i < n1 && j < n2) { 
        if (L[i] <= M[j]) { 
            arr[k] = L[i]; i++; 
        } 
        else { 
            arr[k] = M[j]; 
            j++; 
        } 
        k++; 
    }
Copy the code

Step 4: When we run out of elements in L or M, pick up the remaining elements and put them in A[P… R]

   // Copy the remaining elements in the first array to the primary and subarrays
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
Copy the code

   // Copy the remaining elements of the second array into the primary and subarrays
    while(j < n2) { arr[k] = M[j]; j++; k++; }}Copy the code

Three, code implementation

1. Pseudo-code implementation

Have we reached the end of any subarrays? No: Compares the current elements of two arrays Copy the smaller element into the sorted array move the pointer to the element containing the smaller element Yes: copies all remaining elements of the non-empty arrayCopy the code

2. Java implementation

import java.util.Arrays;

/** * merge sort **@className: MergeSort
 * @date: 2021/6/30 * / to him
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = { 6.5.12.10.9.1 };
        mergeSort(arr, 0, arr.length -1);
        System.out.println(Arrays.toString(arr));
    }

    /** * a recursive call to divide the original array into subarrays *@paramArr Primitive array *@paramP Start index *@paramR End index */
    public static void mergeSort(int[] arr, int p, int r) {
        if (p < r) {
            int q = (p + r) /2;
            mergeSort(arr, p, q);
            mergeSort(arr, q + 1, r); merge(arr, p, q, r); }}public static void merge(int[] arr, int p, int q, int r) {
        // Define two subarrays to hold the elements of the original array
        int n1 = q - p + 1;
        int n2 = r - q;
        int[] L = new int[n1];
        int[] M = new int[n2];
        // Save the elements of the original array to the subarray
        for (int i = 0; i < n1; i++) {
            L[i] = arr[p + i];
        }
        for (int i = 0; i < n2; i++) {
            M[i] = arr[q + 1 + i];
        }
        // Define three Pointers to the indexes of the original and subarrays
        int i = 0;
        int j = 0;
        int k = p;
        // Iterate through the elements of the subarray until the end of the subarray is reached
        while (i < n1 && j < n2) {
            if (L[i] < M[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = M[j];
                j++;
            }
            k++;
        }
        // Save the remaining elements of the subarray to the original array
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while(j < n2) { arr[k] = M[j]; j++; k++; }}}Copy the code

4. Sorting complexity

1. Time complexity

2. Space complexity

• The space is O(n), because you’re putting elements of the original array into two subarrays.

Merge sort application

• Inverse problem
• External sorting
• E-commerce applications

Reference article:

www.programiz.com/dsa/merge-s…