This is the 13th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

We learned about sorting methods in the last article, and we learned more about JavaScript in this series.

In this article, we will continue to learn about sorting methods in JavaScript: sorting algorithms are often used in real work

JavaScript sort algorithm – merge sort

Merge sort is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer.

JS- merge sort – code implementation

function mergeSort(arr) {
  // ...
  // Use a top-down recursive approach
  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))
}
Copy the code

// Utility functions: switch left and right positions

function merge(left, right) {
  var result = []

  while (left.length && right.length) {
    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

Test time:

// Introduce the following method to test the code time:
getFnRunTime(mergeSort)
Copy the code

A function that tests the time it takes for code to run


const testArrFn = function() {
  let arr = []
  const count = 200000
  for (let i = 0; i < count; i++) {
    arr[i] = Math.floor(Math.random() * 50 + 1)}return arr
}
let testArr = testArrFn()

let len = testArr.length
/ * * *@desc Test function execution time */
module.exports = async function getFnRunTime(fn) {
  let startTime = Date.now(),
    endTime
  let result = await fn(testArr)
  endTime = Date.now()
  console.log(testArr, result)
  console.log(
    `total time: ${endTime - startTime}ms, `."test array'length: " + len,
    result.length
  )
}
Copy the code

Read more

  • 】 【 Array. The prototype. The map (),
  • JS- special symbol – bit operator
  • 【ES6 – for/of】,
  • JS- Logical operator – short circuit? ,
  • [JavaScript- arrow function],
  • 】 【 JavaScript – forEach (),
  • JavaScript -sort()
  • 【JavaScript- sort algorithm – Hill sort 】