orderBy benchmark

bench.js

// vue internals
var _ = require('../src/util')
var Path = require('../src/parsers/path')

// original implementation using native sort
var original = function (arr, sortKey, reverse) {
  if (!sortKey) {
    return arr
  }
  var order = 1
  if (arguments.length > 2) {
    if (reverse === '-1') {
      order = -1
    } else {
      order = reverse ? -1 : 1
    }
  }
  // sort on a copy to avoid mutating original array
  return arr.slice().sort(function (a, b) {
    if (sortKey !== '$key' && sortKey !== '$value') {
      if (a && '$value' in a) a = a.$value
      if (b && '$value' in b) b = b.$value
    }
    a = _.isObject(a) ? Path.get(a, sortKey) : a
    b = _.isObject(b) ? Path.get(b, sortKey) : b
    return a === b ? 0 : noTilde(a) > noTilde(b) ? order : -order
  })
}

// PR using merge sort
var mergeSort = function (arr, sortKey, reverse) {
  if (!sortKey) {
    return arr
  }
  var asc = true
  if (arguments.length > 2) {
    if (reverse === '-1') {
      asc = false
    } else {
      asc = !reverse
    }
  }
  
  var getKey = function(item) {
    if (sortKey !== '$key' && sortKey !== '$value') {
      if (item && '$value' in item) item = item.$value
    }
    return _.isObject(item) ? Path.get(item, sortKey) : item
  }

  var merge = function(left, right) {
    var result = []
    while ((left.length > 0) && (right.length > 0)) {
      if (asc) {
        if (noTilde(getKey(left[0])) < noTilde(getKey(right[0]))) {
          result.push(left.shift())
        } else {
          result.push(right.shift())
        }
      } else {
        if (noTilde(getKey(left[0])) > noTilde(getKey(right[0]))) {
          result.push(left.shift())
        } else {
          result.push(right.shift())
        }    
      }
    }
    return result.concat(left, right)
  }

  var sort = function(array) {
    var len = array.length
    if (len < 2) {
      return array
    }
    var pivot = Math.ceil(len / 2)
    return merge(sort(array.slice(0, pivot)), sort(array.slice(pivot)))
  }
  return sort(arr)
}

function noTilde(s) {
  if (!!s) {
    if (typeof s === "number") {
      return s
    } else {
      if (typeof s.normalize !== "undefined") {
        s = s.normalize("NFKD")
      }
      return s.replace(/[\u0300-\u036F]/g, "")
    }
  } else {
    return ""
  }
}

// Benchmarking

var metrics = 0

function benchSingle (fn) {
  var data = []
  for (var i = 0; i < 100; i++) {
    data.push({ id: i })
  }
  shuffle(data)
  var s = Date.now()
  fn(data, 'id')
  metrics += Date.now() - s
}

function bench (n) {
  metrics = 0
  for (var i = 0; i < n; i++) {
    benchSingle(original)
  }
  console.log('original: ' + (metrics / n) + 'ms/op')
  metrics = 0
  for (var i = 0; i < n; i++) {
    benchSingle(mergeSort)
  }
  console.log('mergeSort: ' + (metrics / n) + 'ms/op')
}

// shuffle the data array
function shuffle(array) {
  var currentIndex = array.length, temporaryValue, randomIndex
  while (0 !== currentIndex) {
    randomIndex = Math.floor(Math.random() * currentIndex)
    currentIndex -= 1
    temporaryValue = array[currentIndex]
    array[currentIndex] = array[randomIndex]
    array[randomIndex] = temporaryValue
  }
  return array
}

bench(1000)

Results on my machine:

original: 0.125ms/op
mergeSort: 0.218ms/op