Why is it order nlogn? More on merge sort

Links to articles

Good foundation? Really understand bubbling, selection, insertion sort
How could the performance be better? What you need to know about heap sorting
Why is it order nlogn? More on merge sort

Principle 1.

Merge Sort is a very classic sorting algorithm that utilizes Divide and Conquer. The algorithm is described in a few sentences:

To constantlyBreak upArrays become multiple smallest arrays with only one element, then smallest arraysComparing the twoTo sort,mergeIn orderLarge array

Large arrayContinue the pairwise comparison and merge into multiple sorted onesA larger array

And so on until the entire array is sorted.

With this piece of the graph is the case, to convert,3,8,6,2,7,1,4 [5] through the merge sort,2,3,4,5,6,7,8 [1]

The sorting process can be divided into two steps: Divide and Conquer. In my opinion, governance is not an easy word to understand. In fact, its main work is merger

Split: Divide an array in half into smaller arrays

(1) divide [5,3,8,6,2,7,1,4] into [5,3,8,6] and [2,7,1,4]. (2) divide [5,3,8,6] into [5,3] and [8,6]; (3) [2,7,1,4] is divided into [2,7] and [1,4]; (4) And so on until each array has only one element.

Merge: Merges small arrays by sorting them from smallest to largest

(1) For [5] and [3], after comparing their sizes, merge them into arrays [3,5]; (2) For [8] and [6], after comparing their sizes, merge them into arrays [6,8]; (3) compare the sizes of [3,5] and [6,8] and merge them into arrays [3,5,6,8]; (4) and so on, and finally to,5,6,8 [3] and [1,2,4,7], more after order, merged into the final result,2,3,4,5,6,7,8 [1], the complete order

2. Detailed analysis

This is a little bit easier to do with splitting, so for example, we can userecursiveThe way of

function mergeSort(arr, l, r) { // arr is the complete array, l is the left index, r is the right index
  var mid = l + ((r - 1) / 2); // Get the midpoint
  if (r - l > 1) {  // Recurse until the left index is greater than the right
    mergeSort(arr, l, mid);  // Recursively process the left half of the array
    mergeSort(arr, mid + 1, r); // Recursively process the right half of the array
  }
  merge(arr, l, mid, r); // Do sorting and merging, which will be discussed later
  return arr; // return sort merge result
}
Copy the code

Disassemble a large array by reducing the distance between the indexes L and R until you get a small array with only one element.

After splitting, you need to sort and merge the arrays. The merge method in the code above does this. Take merging [2,7] and [1,4] as an example, see the figure below

Let’s go step by stepmergeIt is a process

For the smallest array[2],[7],[1],[4]

[2]and[7]The comparison,2than7Small, itself sorted, merged into[2, 7];
[1]and[4]Compare, also sorted, merged into[1, 4].

And then merge[2, 7]and[1, 4]In the[2, 7]and[1, 4]Sort before merging.

Through the left pointerleftPoint to the[2, 7]The elements of the2, through the right pointerrightPoint to the[1, 4]One of the most elements1.

Create a new auxiliary arrayHelpAnd compare theArray[4]andArray[6].2than1Big,1In theHelpIn the

Move right pointer right to position 7 to continue comparing Array[4] to Array[7], 2 is less than 4, and place 2 in Help

The left pointer left moves right to position 5, and then compares Array[5] and Array[7]. 7 is larger than 4. Put 4 in Help, and find that right pointer right cannot move right again

[2,7] and [1,4] are sorted and merged by Help.

Finally, brush Help back to the original array to complete the merge of the original array [2,7] and [1,4], and other small arrays, and so on.

3. Code implementation

function main(arr) {
  var l = 0;
  var r = arr.length - 1;
  return mergeSort(arr, l, r);
}

function mergeSort(arr, l, r) {
  var mid = l + ((r - l) >> 1); // Equivalent to l + ((r-1) / 2)
  if (r - l > 1) {
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
  }
  merge(arr, l, mid, r);
  return arr;
}

function merge(arr, l, mid, r) {
  var left = l;
  var right = mid + 1;
  var helpInd = 0;
  var help = [];
  while (left <= mid && right <= r) {
    help[helpInd++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
  }
  while (left <= mid && right > r) {
    help[helpInd++] = arr[left++];
  }
  while (left > mid && right <= r) {
    help[helpInd++] = arr[right++];
  }
  var i = 0;
  while(help[i] ! = =undefined) { arr[l + i] = help[i]; i++; }}console.log(main([5.1.4.3.0])); / /,1,2,3,4,5 [0]
Copy the code

4 Time Complexity

We can calculate the time complexity of merge sort by two methods, namely intuitive understanding and recursive complexity formula

4.1 Intuitive Understanding

If the number of nodes in a binary tree is N, its height is logN + 1. In the split phase, logN operations (log8 = 3) are performed, and the time complexity of this phase is logN

In the merge stage, we need to traverse each node of the binary tree, the number of nodes of each layer is N, and the number of layers to traverse is logN (log8 = 3), so the time complexity of this stage is NlogN

Add the time complexity of the two phaseslogN + NlogN, the time complexity can be obtainedO(NlogN)

4.2 Recursive complexity formula

a * T(\frac{N}{b}) + O(N^d)

If logba>dlog_ba > dlogba>d, the recursive function time complexity is O(Nlogba)O(N^{log_ba})O(Nlogba) if logba

Before introducing the formula, let’s look at the concept of recursive function size, using the recursive function mentioned above as an example

function mergeSort(arr, l, r) { // arr is the complete array, l is the left index, r is the right index
  var mid = l + ((r - 1) / 2); // Get the midpoint
  if (r - l > 1) {  // Recurse until the left index is greater than the right
    mergeSort(arr, l, mid);  // Recursively process the left half of the array
    mergeSort(arr, mid + 1, r); // Recursively process the right half of the array
  }
  merge(arr, l, mid, r); // Do sorting and merging, which will be discussed later
  return arr; // return sort merge result
}
Copy the code

MergeSort has two sub-recursions that deal with the left and right side of the arr array in the parent function, so their recursive function size is 12\frac{1}{2}21.

The formula a∗T(Nb)+O(Nd)a * T(\frac{N}{b}) +O(N ^d)a∗T(bN)+O(Nd) in 1b\ Frac {1}{b}b1 is the scale of the recursive function, a is the number of sub-recursive functions (there are two), So 2∗T(N2)2 * T(\frac{N}{2})2∗T(2N).

Formula a ∗ T (Nb) + O (Nd) a * T (\ frac {N} {b}) + O (N ^ d) a ∗ T (bN) + O (Nd) in the second part O (Nd) O (N ^ d) O (Nd), is the child of recursion beyond the time complexity of the code. For example, in the example above, code other than recursion has

function mergeSort(arr, l, r) { // arr is the complete array, l is the left index, r is the right index
  var mid = l + ((r - 1) / 2); // Get the midpoint
  If (r-l > 1) {// recurse until the left index is greater than the right index
  // mergeSort(arr, l, mid); // Recursively process the left half of the array
  // mergeSort(arr, mid + 1, r); // Recursively process the right half of the array
  // }
  merge(arr, l, mid, r); // Do sorting and merging, which will be discussed later
  return arr; // return sort merge result
}
Copy the code

The merge function is O(N). Well, finally I can plug it into the formula and get it

2 * T(\frac{N}{2}) + O(N)

Where a = 2, b = 2, d = 1

If logba>dlog_ba > dlogba>d, the recursive function time complexity is O(Nlogba)O(N^{log_ba})O(Nlogba) if logba

Log22 =1log_22 =1 log22=1 log22=1, so time is O(NlogN).

The recursive complexity formula works for all recursive functions of the same recursive size, such as the example above where each sub-recursive function is 12\frac{1}{2}21. If be the following kind is inapplicable

function mergeSort(arr, l, r) {
    // ...
   mergeSort(arr, l, (r - l) / 3);  // Recursively process 1/3 of the array
   mergeSort(arr, (r - l) / 3, r); // Recursively process 2/3 of the array
   // ...
}
Copy the code

5. Extra space complexity

During the merge process, we use the helper array Help for sorting arrays before the merge.

In general, because the number of nodes in each layer of the binary tree is constant N, the total number of nodes in all small arrays in each layer is N, and the total space occupied by multiple auxiliary arrays Help is also N.

So, the extra space we need is N, and the extra space complexity is O(N).

Stability of 6.

Stability depends on whether two elements with the same value swap places when sorting.

The algorithm mainly uses the auxiliary array Help to sort in the merge stage. In the process of comparing sizes, if elements with the same value do not need to exchange elements, there will be no change in order in the merge process.

So merge sort algorithm is stable

7. Summary of this chapter

Merge sort is a kind of sorting using divide-and-conquer method, first continuously split the array called the smallest array, and then the smallest array pair comparison, merge into a number of well-ordered larger array, larger pair comparison, merge into a number of well-ordered larger array, until the completion of the whole array sort
Merge sort is going to run in timeO(NlogN)
The space complexity of merge sort is zeroO(N)
Merge sort is stable