quicksort pure js

quicksort.js

Array.prototype.sort = function(compareFN) {

  var compareFN = compareFN || function(a, b) {
    return a - b
  }
  
  var arr = this
  
  function getThirdIndex(from, to) {
    // get suitable pivot
    if (to - from < 1000) {
      return from + ((to - from) >> 1)
    }
    var small_arr = []
    var increment = 200 + ((to - from) & 15)
    for (var i = from + 1; i < to - 1; i += increment) {
      small_arr.push([i, arr[i]])
    }
    small_arr.sort(function(a, b) {
      return compareFN(a[1], b[1])
    })
    return small_arr[small_arr.length >> 1][0]
  }
  
  function quickSort(from, to) {

    while (1) {
    
      if (to - from <= 10) {
        // use insertionsort rather than quicksort
        insertionSort.apply(this, arguments)
        return
      }
    
      var third_index = 0
      third_index = getThirdIndex(from, to)

      var v0 = arr[from]
      var v1 = arr[to - 1]
      var v2 = arr[third_index]
      var c01 = compareFN(v0, v1)
      if (c01 > 0) {
        var tmp = v0
        v0 = v1
        v1 = tmp
      }
      var c02 = compareFN(v0, v2)
      if (c02 >= 0) {
        var tmp = v0
        v0 = v2
        v2 = v1
        v1 = tmp
      } else {
        var c12 = compareFN(v1, v2)
        if (c12 > 0) {
          var tmp = v1
          v1 = v2
          v2 = tmp
        }
      }
      
      // now: v0 < v1 < v2
      arr[from] = v0 // small
      arr[to - 1] = v2 // big
      var pivot = v1 // middle
      var low_end = from + 1
      var high_start = to - 1
      arr[third_index] = arr[low_end]
      arr[low_end] = pivot

      partition: for (var i = low_end + 1; i < high_start; i++) {
        // from  low_end >> === << high_start  to
        // pointers low_end & high_start move to center
        var element = arr[i]
        var order = compareFN(element, pivot)
        if (order < 0) {
          arr[i] = arr[low_end]
          arr[low_end] = element
          low_end++
        } else if (order > 0) {
          do {
            high_start--
            if (high_start == i) break partition
            var top_elem = arr[high_start]
            order = compareFN(top_elem, pivot)
          } while (order > 0)
          arr[i] = arr[high_start]
          arr[high_start] = element
          if (order < 0) {
            element = arr[i]
            arr[i] = arr[low_end]
            arr[low_end] = element
            low_end++
          }
        }
      }

      if (to - high_start < low_end - from) {
        arguments.callee(high_start, to)
        to = low_end
      } else {
        arguments.callee(from, low_end)
        from = high_start
      }
      
    }    
  }
  
  function insertionSort(from , to) {
    for (var i = from + 1; i < to; i++) {
      var element = arr[i]
      for (var j = i - 1; j >= from; j--) {
        var tmp = arr[j]
        var order = compareFN(tmp, element)
        if (order > 0) {
          arr[j + 1] = tmp
        } else {
          break
        }
      }
      arr[j + 1] = element
    }
  }

  quickSort(0, this.length)
}