# Untitled

By: a guest on May 28th, 2012  |  syntax: None  |  size: 1.46 KB  |  hits: 15  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. // insertion sort with bin-search (aka binary sort)
2. var isort = (function () {
3.     var sort = function (buf, first, last, cmp) {
4.         for (var i = first + 1; i < last; i += 1) {
5.             var point = search(buf, first, i, buf[i], cmp);
6.             rotate(buf, point, i + 1);
7.         }
8.     };
9.
10.     // binary search for insert point (rightmost)
11.     // e.g. [2, 4, 6] with 3 => 1
12.     // e.g. [2, 4, 6] with 4 => 2
13.     // e.g. [2, 4, 6] with 5 => 2
14.     // e.g. [2, 4, 6] with 6 => 3
15.     var search = function (buf, first, last, value, cmp) {
16.         while (first < last) {
17.             var mid = (first + last) >> 1;
18.             if (cmp(value, buf[mid])) {
19.                 last = mid;
20.             } else {
21.                 first = mid + 1;
22.             }
23.         }
24.         return first;
25.     };
26.
27.     var rotate = function (buf, first, last) {
28.         if (last - first <= 1) return;
29.         var prev = buf[first];
30.         for (var pointer = last - 1; pointer > first; pointer -= 1) {
31.             buf[pointer] = buf[pointer - 1];
32.         }
33.         buf[first] = prev;
34.     };
35.
36.     var lessThan = function (a, b) {
37.         return a < b;
38.     };
39.
40.     return function isort(buf/*, cmp*/) {
41.         var cmp = arguments[1] || lessThan;
42.         sort(buf, 0, buf.length, cmp);
43.         return buf;
44.     };
45. })();
46.
47.
48. // examples
49. console.log(isort([]));
50. console.log(isort([1]));
51. console.log(isort([1,2]));
52. console.log(isort([2,1]));
53. console.log(isort([1,2,3,4,5]));
54. console.log(isort([5,4,3,2,1]));