sort.js

var arr = [3, 1, 2, 10, 4, 6, 5, 9, 8]

// quick sort
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  var midIdx = Math.floor(arr.length/2)
  var midVal = arr[midIdx]
  var left = []
  var right = []

  for (let i = 0; i < arr.length; i++) {
    if (i === midIdx) continue
    if (arr[i] < midVal) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }

  return quickSort(left).concat(midVal, quickSort(right))
}

// merge sort
function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr
  }

  var midIdx = ~~(arr.length / 2)
  var left = arr.slice(0, midIdx)
  var right = arr.slice(midIdx, arr.length)

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

  while(left.length >= 1 && right.length >= 1) {
    if (left[0] < right[0]) {
      result.push(left.shift(0))
    } else {
      result.push(right.shift(0))
    }
  }

  if (left.length) {
    result = result.concat(left)
  }
  if (right.length) {
    result = result.concat(right)
  }

  return result
}

// insertion sort
function insertionSort(arr) {
  var result = [arr[0]]

  for (let i = 1; i < arr.length; i++) {
    for (var j = 0; j < result.length; j++) {
      if (arr[i] < result[j]) {
        result.splice(j, 0, arr[i])
        break
      }
    }
    if (j === result.length) {
      result[j] = arr[i]
    }
  }

  return result
}

// selection sort
function selectionSort(arr) {
  var result = []
  while (arr.length) {
    var min = Math.min(...arr)
    result.push(min)
    arr.splice(arr.indexOf(min), 1)
  }
  return result
}

// bubble sort
function bubbleSort(arr) {
  var arr = arr.concat()
  var len = arr.length
  while (len >= 2) {
    for (let i = 0; i < len - 1; i++) {
      if (arr[i] > arr[i+1]) {
        var tmp = arr[i]
        arr[i] = arr[i+1]
        arr[i+1] = tmp
      }
    }
    len--
  }
  return arr
}

class MinHeap {
  constructor(arr) {
    this.arr = []
    if (Array.isArray(arr)) {
      arr.forEach(item => {
        this.add(item)
      })
    }
  }

  add(item) {
    const nextIdx = this.arr.push(item)
    this.heapifyUp(nextIdx - 1)
  }

  poll() {
    const minItem = this.arr.shift()
    this.swap(this.arr.length - 1, 0)
    this.heapifyDown()
    return minItem
  }

  heapifyDown(curIdx) {
    let idx = curIdx || 0
    while (this.hasLeftChild(idx)) {
      const parent = this.arr[idx]
      const leftChild = this.getLeftChild(idx)
      let rightChild
      let smaller
      if (this.hasRightChild(idx)) {
        rightChild = this.getRightChild(idx)
        smaller = Math.min(parent, leftChild, rightChild)
      } else {
        smaller = Math.min(parent, leftChild)
      }
      const smallerIdx = this.arr.indexOf(smaller)
      if (smallerIdx !== idx) {
        this.swap(smallerIdx, idx)
        this.heapifyDown(idx)
      } else {
        break
      }
    }
  }

  heapifyUp(curIdx) {
    let idx = curIdx

    while (this.hasParent(idx) && this.getParent(idx) > this.arr[idx]) {
      const parent = this.getParent(idx)
      const parentIdx = this.arr.indexOf(parent)
      this.swap(parentIdx, idx)
      idx = parentIdx
    }
  }

  hasParent(idx) {
    return !(idx === 0)
  }
  hasLeftChild(idx) {
    return (idx + 1) * 2 <= this.arr.length
  }
  hasRightChild(idx) {
    return ((idx + 1) * 2 + 1) <= this.arr.length
  }
  getParent(idx) {
    const parentIdx = Math.floor((idx - 1) / 2)
    return this.arr[parentIdx]
  }
  getLeftChild(idx) {
    return this.arr[(idx + 1) * 2 - 1]
  }
  getRightChild(idx) {
    return this.arr[(idx + 1) * 2]
  }
  swap(one, two) {
    const tmp = this.arr[one]
    this.arr[one] = this.arr[two]
    this.arr[two] = tmp
    return this
  }

  print() {
    console.log(this.arr)
  }
}
function heapSort(arr) {
  var minHeap = new MinHeap(arr)
  // minHeap.print()
  const result = []
  for (let i = 0, length = minHeap.arr.length; i < length; i++) {
    result.push(minHeap.poll())
  }
  return result
}

(function() {
  console.log(heapSort(arr))
})()