0005: Algorithm — Merge sort

algorithm

Divide the array into equal length love song subarrays and merge sort the subarrays

Time complexity

$(n/2) + ((2^2-1) * n/(2^2)) + … + (n-1) = O(nlogn)$

js

const input = [4.2.15.2.5.6.21.67.2.3]
const sort = (arr = []) = > {
    if (arr.length === 1) return arr
    if (arr.length === 2) {
      return [Math.min(... arr),Math.max(... arr)] }const middle = Math.floor(arr.length / 2)
    const sortedA = sort(arr.slice(0, middle))
    const sortedB = sort(arr.slice(middle))
    const result = [];
    while(sortedA.length && sortedB.length) {
      const a = sortedA.shift();
      const b = sortedB.shift();
      if (a < b) {
        result.push(a)
        sortedB.unshift(b);
      } else{ result.push(b) sortedA.unshift(a); }}return result.concat(sortedA).concat(sortedB)
}
console.log(sort(input))
Copy the code