bubble_vs_merge_sort.js

/**
 * n = 20
 * 
 * test merge: 0.517ms
 * test bubble: 0.204ms
 * 
 * n = 100
 * 
 * test merge: 3.295ms
 * test bubble: 1.395ms
 * 
 * n = 1000
 * 
 * test merge: 52.568ms
 * test bubble: 205.666ms
 * 
 * n = 10000
 * 
 * test merge: 147.363ms
 * test bubble: 15928.640ms
 */
const randomInt = (min = 0, max = 100) => Math.floor(Math.random() * (max - min + 1)) + min

const bubbleSort = arr => {
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j+1]) {
        arr.splice(j, 2, arr[j+1], arr[j])
      }
    }
  }
  
  return arr
}

const mergeSort = arr => {
  if (arr.length < 2) return arr

  const middleIdx = Math.floor(arr.length / 2)

  let left = arr.splice(0, middleIdx)
  let right = arr.splice(0)

  return merge(mergeSort(left), mergeSort(right))
}

const merge = (arr1, arr2) => {
  const res = []

  while (arr1.length && arr2.length) {
    if (arr1[0] < arr2[0]) {
      res.push(arr1.splice(0, 1)[0])
      continue
    } 
    res.push(arr2.splice(0, 1)[0])
  }

  return res.concat(arr1, arr2)  
}

const length = 10000
const arrToSort = []

for (let i = 0; i < length; i++) {
  arrToSort.push(randomInt())
}

console.time('test merge')
const res = mergeSort([...arrToSort]);
console.timeEnd('test merge')

console.time('test bubble')
const res1 = bubbleSort([...arrToSort]);
console.timeEnd('test bubble')