Merge sort uses the idea of divide and conquer. First, it divides an array into two smaller arrays repeatedly until each array has only one element. The second is “rule”, starting with the smallest array and merging them in size order until they are the same size as the original array

Merge sort

Merge-sort is a sorting method based on the idea of divide-and-conquer. The algorithm adopts the classic divide-and-conquer strategy (divide problems into small problems and solve them recursively). The Conquer phase “tinkered” with the answers obtained in the conquer phases, i.e. divide and conquer.

points

“Divide” is to divide the original array until there is only one element left in each array. The array of each element is naturally ordered, so the process of “conquer” can begin.

cure

“Cure” actually merges already ordered arrays into larger ordered arrays. So how do you do that? Create a new array, compare left[0] and right[0], put the value of that smaller array into the new array, and then continue to compare left[0] and right[1], or left[1] and right[0]. We can see that both the left and right arrays only need to be traversed once, so sorting two ordered arrays takes O(n) time.

Algorithm description

  • The input sequence of length N is divided into two subsequences of length N /2.
  • Merge sort is used for these two subsequences respectively.
  • Combine two sorted subsequences into a final sorted sequence.

Dynamic graph display

Time complexity analysis: the dividing process needs three steps: log8 = 3, and each step needs to traverse 8 elements once, so 8 elements need to run 8log8 times in total, so for n elements, the time complexity is O(nlogn).

Code implementation

Js version:

function mergeSort(arr) {
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right) {
    var result = [];
 
    while(left.length>0 && right.length>0) {
        if(left[0] <= right[0]) {
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
 
    while(left.length)
        result.push(left.shift());
 
    while(right.length)
        result.push(right.shift());
 
    return result;
}
Copy the code

Java version:

Static void merge_sort_recursive(int[] arr, int[] result, int start, int end) { if (start >= end) return; int len = end - start, mid = (len >> 1) + start; int start1 = start, end1 = mid; int start2 = mid + 1, end2 = end; merge_sort_recursive(arr, result, start1, end1); merge_sort_recursive(arr, result, start2, end2); int k = start; while (start1 <= end1 && start2 <= end2) { result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; } while (start1 <= end1) { result[k++] = arr[start1++]; } while (start2 <= end2) { result[k++] = arr[start2++]; } for (k = start; k <= end; k++) { arr[k] = result[k]; } } public static int[] merge_sort2(int[] arr) { int len = arr.length; int[] result = new int[len]; merge_sort_recursive(arr, result, 0, len - 1); return result; }Copy the code

DORA sister [ITI2018] front-end fishing technology group

Welcome everyone technical exchange push touch fish help all can – link

Series of links (will be updated later)

  • Finally understand Hill sort and insertion sort

  • Figure out quicksort

  • Insertion Sort

  • The difference between bubble sort and selection sort