Having nothing to do, I wrote six common sorting algorithms and recorded my essays;

1. Bubble sorting

Exchange sorting, compare two adjacent numbers, and move the small one forward, just like a bubble. Time complexity O(n^2), stable.

const bubble_sort = function(arr){
    const {length} = arr;
    for(let i = length - 1; i > 0; i --){      
      for(let j = length - 1; j >= 0; j -- ){
        if(arr[j] < arr[j-1])
          [arr[j-1], arr[j]] = [arr[j], arr[j-1]]       
      }
    }
    return arr;
 }

2. Insert sort

Set the first value as the ordered sequence, start from the second value, take values in turn, insert them into the appropriate position in the ordered sequence, and finally get the sorting result. The time complexity is O(n^2), which is stable.

const insert_sort = function(arr){
    const {length} = arr;
    for(let i = 1; i < length; i++) {
      for(let j = i; j > 0; j --) {//Ordered sequence to maintain
        if(arr[j] < arr[j-1]){
          [arr[j-1], arr[j]] = [arr[j], arr[j-1]]
        }
      }
    }
    return arr;
  }

3. Select sort

Select the minimum (large) value in the array to exchange with the value at the end of the ordered sequence in turn. For example, the first time is to find the minimum (large) value and the number of the first position to exchange positions. The event complexity is O (n^2), which is unstable.

 const choose_sort = function(arr){
    const {length} = arr;
    for(let i = 0; i < length; i++){
      let min_index = i;
      for(let j = i; j < length; j ++){
        min_index = arr[j + 1] < arr[min_index] ? j+1 : min_index;       
      }
      [arr[i], arr[min_index]] = [arr[min_index], arr[i]]
    }
    return arr;
  }

4. Quick sort

Fast sorting adopts divide and conquer method, which is also a kind of exchange sorting. It is an optimized version of bubble sorting. Select a base value, put the smaller one on its left and the larger one on its right through comparison and exchange, find a base value for the two sequences obtained, continue to do comparison and exchange, and return in turn. Time complexity O(nlog2n) ~ O (n^2), unstable.

const quick_sort = function(arr){
    let {length} = arr;
    const sort = (subArr, left = 0, right = length - 1)=>{
      if(left >= right) return;
      let key = subArr[left]; 
      let first = left;     
      let last = right;
      while(left < right){
        while(subArr[left] <= key && left < right) {
          left ++;
        }
        while(subArr[right] >= key && left < right) {
          right --;
        }
        [subArr[left], subArr[right]] = [subArr[right], subArr[left]];
      }
      sort(subArr, first, right-1);
      sort(subArr, right, last)
    }
    sort(arr);
    return arr;

  }

5. Heap sort

Heap sorting is a kind of selective sorting. Heap actually regards the sequence as a complete binary tree. The end nodes that have never been sorted recurs to the root node in turn, and compares and replaces the values of child nodes and parent nodes to ensure that the value of parent nodes is always greater (less) than or equal to that of child nodes, so as to get a large (less) top heap, Then exchange the value of the root node with the value of the unordered end node (the nodes exchanged with the root node form an ordered sequence), and then continue the next round of large (small) top heap adjustment. Time complexity O(nlog2n), unstable.

const heap_sort = function(arr){
    const {length} = arr;
    const changeMax = (sub_arr, root, limit) => {
      let l_child = 2 * root + 1,
      r_child = 2  * root + 2;
      
      let max_child = r_child <= limit && sub_arr[l_child] < sub_arr[r_child] ? r_child : l_child;
      if(max_child <= limit && sub_arr[root] < sub_arr[max_child]) {
        [sub_arr[root], sub_arr[max_child]] = [sub_arr[max_child], sub_arr[root]]
      }    
    }

    for(let i = length - 1; i >= 0; i--){
      for(let j = Math.round(i/2) -1; j >= 0; j --){
        changeMax(arr, j, i)
      }
      [arr[i], arr[0]] = [arr[0],arr[i]]
    }
    return arr;
    
  }

6. Merge sort

Merge sort also becomes merge sort. Divide the sequence into n (sequence length) small sequences, and then merge in pairs to get [n/2] ordered small sequences, and then merge in pairs, and cycle in turn until all ordered sequences are combined into one, and finally get an ordered sequence with length n. Time complexity O(nlog2n), stable.

const merge = (left, right) => {
      let result = [];
      
      while(left.length > 0 && right.length > 0){
        if(left[0] <= right[0]){
          result.push(left.shift());      
        } else {
          result.push(right.shift());     
        }
      }
      if(left.length > 0){
        result.push(...left)
      }
      if(right.length > 0){
        result.push(...right)
      }
      return result;
    }
  const merge_sort = function(arr){
    const {length : l} = arr;
    if(l < 2) return arr;
    const middle = Math.floor(l / 2),
      left_arr = arr.slice(0, middle),
      right_arr = arr.slice(middle, l);
    return merge(merge_sort(left_arr),merge_sort(right_arr));  
  }

Summary:

Complexity and stability of sorting algorithm

category	method	Time complexity		Spatial complexity	stability
		worst	average	Secondary storage
Insert sort		O(n^2)	O(n^2)	O(1)	stable
Merge sort		O(nlog2n)	O(nlog2n)	O(n)	stable
choice	Select sort	O(n^2)	O(n^2)	O(1)	instable
	Heap sort	O(nlog2n)	O(nlog2n)	O(1)	instable
exchange	Bubble sorting	O(n^2)	O(n^2)	O(1)	stable
	Quick sort	O(n^2)	O(nlog2n)	O(1)	instable