Three-way radix quicksort

RadixQuicksort.scala

import java.util.Arrays

// Three-way radix quicksort aka Multi-key quicksort
//
// Fast Algorithms for Sorting and Searching Strings
// http://www.cs.princeton.edu/~rs/strings/paper.pdf

object RadixQuicksort {

  def sort(arr: Array[String]) =
    sort0(arr, 0, arr.length, 0)

  def sort(arr: Array[String], from: Int, to: Int) =
    sort0(arr, from, to-from, 0)

  def sort(arr: Array[String], from: Int, to: Int, depth: Int) =
    sort0(arr, from, to-from, depth)

  private def charAt(str: String, depth: Int): Int =
    if (str.length == depth) -1 else str.charAt(depth)

  private def sort0(arr: Array[String], base: Int, len: Int, depth: Int): Unit = {

    // |---equal---|---lt---|---not yet partitioned---|---gt---|---equal---|
    //            aEq       a                         b       bEq

    if (len <= 1)
      return

    var r = util.Random.nextInt(len)

    swap(arr, base, base+r)
    val pivot = charAt(arr(base), depth)

    var aEq = base
    var a   = base
    var b   = base + len - 1
    var bEq = base + len - 1

    do {
      while (a <= b && charAt(arr(a), depth) <= pivot) {
        if (charAt(arr(a), depth) == pivot) {
          swap(arr, aEq, a)
          aEq += 1
        }
        a += 1
      }

      while (a <= b && charAt(arr(b), depth) >= pivot) {
        if (charAt(arr(b), depth) == pivot) {
          swap(arr, bEq, b)
          bEq -= 1
        }
        b -= 1
      }

      if (a <= b) { // if (a > b) break
        swap(arr, a, b)

        a += 1
        b -= 1
      }
    } while (a <= b)

    val aEqLen = math.min(aEq-base, a-aEq)
    vecswap(base, a-aEqLen, aEqLen, arr);

    val bEqLen = math.min(bEq-b, base+len-bEq-1)
    vecswap(a, base+len-bEqLen, bEqLen, arr);

    r = a-aEq
    sort0(arr, base, r, depth)

    if (charAt(arr(base+r), depth) != -1) {
      sort0(arr, base + r, aEq + len-bEq-1, depth+1)
    }

    r = bEq-b
    sort0(arr, base + len-r, r, depth)
  }

  private def swap(arr: Array[String], a: Int, b: Int) = {
    val x = arr(a)
    arr(a) = arr(b)
    arr(b) = x
  }

  private def vecswap(i: Int, j: Int, len: Int, arr: Array[String]): Unit = {
    var nn = len
    var ii = i
    var jj = j
    while (nn > 0) {
      swap(arr, ii, jj)
      ii += 1
      jj += 1
      nn -= 1
    }
  }

}