preface

Reading “learning JavaScript data structure and algorithm (3rd edition)” have a feeling that I hope every time learning algorithm can output a blog, income column, check their own learning situation ~ article has a mistake welcome various big god correction, don’t spray, if you want to spray, trouble light, thank you ~

start

Merge sort is the first sorting algorithm that can be used in practice. The performance of bubble, select and insert sort is not good, and the performance of merge sort is good. The time complexity O(n·log(n)) is achieved while maintaining stability.

Merge sort is a divide-and-conquer algorithm. The idea is to cut the original array into smaller arrays until each of the smaller arrays has only one location, and then merge the smaller arrays into larger arrays until there is only one sorted large array. Use space for time, which makes it very suitable in some situations where sorting efficiency and stability are more important than storage space (such as in-database sorting, compared with heap sort, merge sort stability is an advantage). And merge sort is very good for linked list sort.

  • The idea of divide and rule
  • Space for time, and it’s stable, and it’s stable, that’s the beauty of it
  • Binary thinking

Train of thought

Such as an array,7,6,5,4,3,2,1 [8]

  • Divide: divide two arrays in half by the figure above and continue to divide them recursively until the array length =1
  • Return: while splitting while sorting, starting from the smallest array item comparison left and right two array items, a new empty array, each comparison to take out a relatively small element into the new array. I keep recursing to get the left and right arrays sorted
  • And: Finally merge the respective new arrays

implementation

function mergeSort(array) {
  if (array.length <= 1) return array; // If the array length is 1, return it directly. Wait until sort merge in merge
  var m = Math.floor(array.length / 2);
  var left = mergeSort(array.slice(0, m)); // The left array is finally sorted through recursive calls
  var right = mergeSort(array.slice(m, array.length)); // The right array is finally sorted through recursive calls
  var arr = merge(left, right); // Merge left and right arrays
  return arr;
}
// Sort and merge left and right arrays
function merge(left, right) {
  var resArr = [], // A new empty array
    i = 0,
    j = 0
  // Each comparison takes a relatively small element and puts it into resArr
  while (i < left.length && j < right.length) { 
    if (left[i] < right[j]) {
      resArr.push(left[i])
      i++;
    } else{ resArr.push(right[j]) j++; }}// At the end of the loop, an array may have a surplus (it is possible that all of the items in one array are larger than the other array and are not pushed at all) appended to the resulting array
  if(i < left.length) { resArr.push(... left.slice(i)) }else{ resArr.push(... right.slice(j)) }return resArr
}

var arr = [8.7.6.5.4.3.2.1];
console.log(mergeSort(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
Copy the code

To optimize the

  • Let me simplify it a little bit
  • witharray.splicereplacearray.sliceReduce space consumption by half.

    slice(start,end)Method returns the selected element from an existing array,Returns a new array, containing array elements from start to end (without the element).

    splice()Method to add or remove items to or from an array,Returns the deleted item. (This method changes the array)
function mergeSort(array) {
  if (array.length <= 1) return array; // If the array length is 1, return it directly. Wait until sort merge in merge
  var m = Math.floor(array.length / 2);
  var left = mergeSort(array.slice(0, m)); // The left array is finally sorted through recursive calls
  var right = mergeSort(array.slice(m, array.length)); // The right array is finally sorted through recursive calls
  return merge(left, right);
}
// Sort and merge left and right arrays
function merge(left, right) {
  var resArr = [] // A new empty array
  while (0 < left.length && 0 < right.length) { // Each comparison takes a relatively small element and puts it into resArr
    resArr.push(left[0] <= right[0]? left.shift() : right.shift())// array.shift() takes the first number and removes the first number in the array
  }
  return resArr.concat(left, right);
}

var arr = [8.7.6.5.4.3.2.1];
console.log(mergeSort(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]
Copy the code

The complexity of the

Merge sort requires extra space, space complexity is O(n), not local sort, equal elements do not swap order, so it is stable sort. The time complexity is O(n·log(n)), which is an excellent algorithm

other

# Front-end algorithm learning – Algorithm complexity # Front-end required algorithm (1) : bubble sort # Front-end required algorithm (2) : select sort # Front-end required algorithm (3) : Insert sort

The last

# Elegant JavaScript sorting algorithm (ES6)