Implementing async quicksort with generators

asynchronous-quick-sort.js

'use strict'

/*
 * QuickSort algorithm adapted from here:
 * http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/
 */

var co = require('co')

function swap(items, firstIndex, secondIndex){
  var temp = items[firstIndex];
  items[firstIndex] = items[secondIndex];
  items[secondIndex] = temp;
}

function* partition(items, left, right) {
  var pivot = items[Math.floor((right + left) / 2)]
  while (left <= right) {
    while (items[left] < pivot) { left++ }
    while (items[right] > pivot) { right-- }
    if (left <= right) {
      swap(items, left, right)
      left++
      right--
    }
    yield true
  }
  return left
}

function* generatorQuickSort(items, left, right) {
  var index
  if (items.length > 1) {
    left = typeof left !== "number" ? 0 : left
    right = typeof right !== "number" ? items.length - 1 : right
    index = yield* partition(items, left, right)
    if (left < index - 1) { yield* generatorQuickSort(items, left, index - 1) }
    if (index < right) { yield* generatorQuickSort(items, index, right) }
  }
  return items
}

function syncQuickSort(items) {
  let copy = items.slice()
  for (let operation of generatorQuickSort(copy));
  return copy;
}

function asyncQuickSort(items, batch) {
  // Note: using co as a temporary stand-in
  // until async/await are available
  return co(function*() {
    let copy = items.slice()
      , counter = 0
      , tick = Promise.resolve()
    for (let operation of generatorQuickSort(copy)) {
      if (!batch || ++counter % batch === 0) {
        yield tick
      }
    }
    return copy;
  })
}

var list = []

for (let i=0; i<1000; i++) {
  list.push(Math.random())
}

console.log(syncQuickSort(list))

asyncQuickSort(list, 1).then(function(sorted) {
  console.log(sorted)
})

nice