bench.js

// vue internals
var _ = require('../util')
var Path = require('../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
  })
}
 
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 sort = function(arr) {
    var len = arr.length;
    if (len <= 1) return arr
    var pivot = Math.ceil(len/2)
    var arr1 = arr.slice(0, pivot)
    var arr2 = arr.slice(pivot)

    // Recursively sort each subarray
    arr1 = sort(arr1)
    arr2 = sort(arr2)

    // Merge sorted subarrays
    return asc ? mergeSortMergeAsc(arr1, arr2, sortKey) : mergeSortMergeDesc(arr1, arr2,sortKey)   
  }
  return sort(arr);
}

function getKey(item, sortKey) {
  if (sortKey !== '$key' && sortKey !== '$value') {
    if (item && '$value' in item) item = item.$value
  }
  return _.isObject(item) ? Path.get(item, sortKey) : item
}


function mergeSortMergeAsc(arr1, arr2, sortKey){
  // Revert subarrays so that lowest element are at end
  arr1.reverse()
  arr2.reverse()

  // Init variables
  var arr = []
  var l1 = arr1.length - 1
  var l2 = arr2.length - 1

  // While still have elements to process
  while(l1 >= 0 || l2 >= 0){
    // If both arrays have elements
    if (l1 >= 0 && l2 >= 0) {
      // Take smallest value
      if (noTilde(getKey(arr1[l1], sortKey)) > noTilde(getKey(arr2[l2],sortKey))) {
        arr.push(arr2[l2])
        l2 -= 1
      } else {
        arr.push(arr1[l1])
        l1 -= 1
      }
    // If elements left only in first subarray
    } else if (l1 >= 0) {
      arr.push(arr1[l1])
      l1 -= 1
    // If elements left only in secnd subarray
    } else {
      arr.push(arr2[l2])
      l2 -= 1
    }
  }
  return arr
}

function mergeSortMergeDesc(arr1, arr2, sortKey){
  // Revert subarrays so that lowest element are at end
  arr1.reverse()
  arr2.reverse()

  // Init variables
  var arr = []
  var l1 = arr1.length - 1
  var l2 = arr2.length - 1

  // While still have elements to process
  while(l1 >= 0 || l2 >= 0){
    // If both arrays have elements
    if (l1 >= 0 && l2 >= 0) {
      // Take smallest value
      if (noTilde(getKey(arr1[l1], sortKey)) < noTilde(getKey(arr2[l2],sortKey))) {
        arr.push(arr2[l2])
        l2 -= 1
      } else {
        arr.push(arr1[l1])
        l1 -= 1
      }
    // If elements left only in first subarray
    } else if (l1 >= 0) {
      arr.push(arr1[l1])
      l1 -= 1
    // If elements left only in secnd subarray
    } else {
      arr.push(arr2[l2])
      l2 -= 1
    }
  }
  return arr
}
 
function noTilde(s) {
  if (typeof s === "string") {
    if (typeof s.normalize !== "undefined") {
      s = s.normalize("NFKD")
    }
    return s.replace(/[\u0300-\u036F]/g, "")
  } else {
    return s
  }
}
 
// Benchmarking
 
var metrics = 0
 
function makeid() {
    var text = "";
    var possible = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

    for( var i=0; i < 5; i++ )
        text += possible.charAt(Math.floor(Math.random() * possible.length));

    return text;
}

function benchSingle (fn) {
  var data = []

  // at 100 elements sorting by string, mergesort starts to get faster than native sort
  for (var i = 0; i < 100; i++) {
    data.push({ id: makeid() })
  }
  shuffle(data)
  var s = Date.now()
  fn(data, 'id', true)
  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)