thelinuxlich · August 29, 2015 14:22 · May 31, 2015 · May 31, 2015
diff --git a/bench.js b/bench.js
@@ -1,7 +1,7 @@
 // vue internals
-var _ = require('../src/util')
-var Path = require('../src/parsers/path')
-
+var _ = require('../util')
+var Path = require('../parsers/path')
+ 
 // original implementation using native sort
 var original = function (arr, sortKey, reverse) {
   if (!sortKey) {
@@ -26,12 +26,12 @@ var original = function (arr, sortKey, reverse) {
     return a === b ? 0 : noTilde(a) > noTilde(b) ? order : -order
   })
 }
-
-// PR using merge sort
-var mergeSort = function (arr, sortKey, reverse) {
+
+var mergeSort = function(arr, sortKey, reverse){
   if (!sortKey) {
     return arr
   }
+
   var asc = true
   if (arguments.length > 2) {
     if (reverse === '-1') {
@@ -41,74 +41,139 @@ var mergeSort = function (arr, sortKey, 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 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);
+}
 
-  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())
-        }
+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 {
-        if (noTilde(getKey(left[0])) > noTilde(getKey(right[0]))) {
-          result.push(left.shift())
-        } else {
-          result.push(right.shift())
-        }    
+        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 result.concat(left, right)
   }
+  return arr
+}
+
+function mergeSortMergeDesc(arr1, arr2, sortKey){
+  // Revert subarrays so that lowest element are at end
+  arr1.reverse()
+  arr2.reverse()
 
-  var sort = function(array) {
-    var len = array.length
-    if (len < 2) {
-      return array
+  // 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
     }
-    var pivot = Math.ceil(len / 2)
-    return merge(sort(array.slice(0, pivot)), sort(array.slice(pivot)))
   }
-  return sort(arr)
+  return 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, "")
+  if (typeof s === "string") {
+    if (typeof s.normalize !== "undefined") {
+      s = s.normalize("NFKD")
     }
+    return s.replace(/[\u0300-\u036F]/g, "")
   } else {
-    return ""
+    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: i })
+    data.push({ id: makeid() })
   }
   shuffle(data)
   var s = Date.now()
-  fn(data, 'id')
+  fn(data, 'id', true)
   metrics += Date.now() - s
 }
-
+ 
 function bench (n) {
   metrics = 0
   for (var i = 0; i < n; i++) {
@@ -121,7 +186,7 @@ function bench (n) {
   }
   console.log('mergeSort: ' + (metrics / n) + 'ms/op')
 }
-
+ 
 // shuffle the data array
 function shuffle(array) {
   var currentIndex = array.length, temporaryValue, randomIndex
@@ -134,5 +199,5 @@ function shuffle(array) {
   }
   return array
 }
-
+ 
 bench(1000)
diff --git a/bench.js b/bench.js
@@ -0,0 +1,138 @@
+// 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)