1. Algorithm introduction

MergeSort is an efficient and stable 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. Merge sort algorithm time complex read O(NLogN), is a stable sorting algorithm.

2. Code implementation of recursive algorithm

/** * merge sequence helper function *@param {Array} Arr the array that needs to be sorted *@param {Number} LeftStartPos The starting value * of the left index of the currently merged sequence@param {Number} RightStartPos Right line start value * of the current merged sequence@param {Number} RightEndPos the end value of the right index of the currently merged sequence */
function merge(arr, leftStartPos, rightStartPos, rightEndPos) {
  // Remember the starting position of the current sequence in the array sequence
  var pos = leftStartPos;
  // Remember the sum of the current two sequences
  var length = rightEndPos - leftStartPos + 1;
  // The end of the left sequence
  var leftEndPos = rightStartPos - 1;
  // a temporary sequence is used to store the result of merging subsequences
  var newArr = [];
  while (leftStartPos <= leftEndPos && rightStartPos <= rightEndPos) {
    // If the value of sequence A is smaller than that of sequence B, merge the values of sequence A first. This will sort the data from smallest to largest
    if (arr[leftStartPos] <= arr[rightStartPos]) {
      newArr[pos++] = arr[leftStartPos++];
    } else{ newArr[pos++] = arr[rightStartPos++]; }}If A is longer than B, merge the rest of A
  while (leftStartPos <= leftEndPos) {
    newArr[pos++] = arr[leftStartPos++];
  }
  If B is longer than A, merge the rest of B
  while (rightStartPos <= rightEndPos) {
    newArr[pos++] = arr[rightStartPos++];
  }
  
  /* Since we don't know the starting position of the left sequence and the starting position of the right sequence when the two subsequences are merged, the simple way to think about it is to copy the data from the right to the left. The total length of the copy is the length of the two sequences and */
  for (var i = 0; i < length; i++, rightEndPos--) { arr[rightEndPos] = newArr[rightEndPos]; }}/** * the auxiliary function for merge sort *@param {Array} Arr the array that needs to be sorted *@param {Number} Left starting index * of the left array@param {Number} The right end index of the right array */
function _mergeSort(arr, left, right) {
  // If the start position is the same as or larger than the end position, there is no point in continuing the merge
  if (left >= right) {
    return;
  }
  var center = Math.floor((left + right) / 2);
  // Continue merging along the left sequence
  _mergeSort(arr, left, center);
  // Continue merging along the right sequence
  _mergeSort(arr, center + 1, right);
  // Merge the left and right sequences that are currently sorted
  merge(arr, left, center + 1, right);
}

/** * unified external interface, reserve simple call interface */ for external
function mergeSort(arr) {
  if (!Array.isArray(arr)) {
    throw new Error("can not sort");
  }
  return _mergeSort(arr, 0, arr.length - 1);
}

Copy the code

3. Sorting ideas of recursive algorithm

The key idea of merge sort is to merge two ordered subsequences

3.1 Merge two ordered sequences

Suppose we now have two ordered subsequences a: [1,2,8,14,15], b: [6, 7, 10], merge two subsequences we need three variables to remember posA, posB, and the current merged position in the new array.

1. Initial state

2. Compare sizes and decide which sequence values to merge into the new sequence

(posA++) (posA++) (posA++) (posA++) (posA++) (posA++) (posA++)

3. Merge a sequence and insert the remaining sequence directly into the new sequence

4. Complete the merger

3.2 Divide and conquer

Step1

Suppose we have the following test data: [2, 7, 3, 5, 8, 4, 10, 9, 1] First, we split our array in two to get two subsequences.

Step2

We find that the left subsequence can continue, so we continue (recursively along the left sequence).At this point, we can see that the dichotomy is no longer possible. At this point, we have two sequences,[2] and [7], and we can consider this sequence to be sorted. So you can merge directly.

Step3

At this point we’ve sorted some of the pieces

Step4

3, summarize

Merge sort of sample code is my a way of implementation, and you realize there are some differences between written (this paper mentioned about the sequence of all is a section on the original array, by passing in a pointer position determine), readers need not constrained at this, as long as to master its core principle, you can try to implement according to the coding implementation of his thoughts, in a word, understand first, Don’t just swallow it and memorize it (if you don’t understand the idea of the algorithm, you’ll forget it over time).

Due to the limited level of the author, it is inevitable that there will be mistakes in the writing process. If there are any mistakes, please correct them. Please contact the author at [email protected], your opinions will help me make better progress. This article is the author’s original, if reproduced please contact the author.