dualPivotQuickSort.swift

// Vladimir Yaroslavskiy's Dual-pivot quick sort.
// Optimization based on [Dart implementation].

public func dualPivotQuickSort<T : Comparable>(inout a: [T]) {
  dualPivotQuickSort(&a) { $0 < $1 }
}

public func dualPivotQuickSort<T>(inout a: [T], isOrderedBefore: (T, T)->Bool) {
  dualPivotQuickSort(&a, indices(a), isOrderedBefore)
}

public func dualPivotQuickSort<T : Comparable>(inout a: [T], range: Range<Int>) {
  dualPivotQuickSort(&a, range) { $0 < $1 }
}

public func dualPivotQuickSort<T>(inout a: [T], range: Range<Int>, isOrderedBefore: (T, T)->Bool) {
  let start = range.startIndex, end = range.endIndex
  let d = end - start
  if d <= 1 { return }
  
  if d < _InsertionSortThreshold {
    return insertionSort(&a, range, isOrderedBefore)
  }
  
  let left = start, right = end - 1
  
  // Choose pivots
  // Take 5 indices, choose 2nd and 4th after sorting them.
  let sixth = d/6
  let idx1 = left + sixth, idx5 = right - sixth
  let idx3 = left + (right - left)/2 // (left + right)/2
  let idx2 = idx3 - sixth, idx4 = idx3 + sixth
  
  // Sorts 5 inputs by 7 comparisons
  sort5(&a[idx1], &a[idx2], &a[idx3], &a[idx4], &a[idx5], isOrderedBefore)
  
  /// (x < y) ? -1 : (x > y) ? 1 : 0
  let cmp: (T, T)->Int = {
    isOrderedBefore($0, $1) ? -1 : isOrderedBefore($1, $0) ? 1 : 0
  }
 
  // Save and move the pivots out
  let P1 = a[idx2], P2 = a[idx4]
  let pivotsEqual = cmp(P1, P2) == 0
  a[idx2] = a[left]
  a[idx4] = a[right]
  
  var less = left + 1   // First index of middle, lesser border.
  var great = right - 1 // Last valid index of middle, greater border.
  
  // Partition
  if pivotsEqual {
    // If P1 == P2, the partioning becomes a [Dutch National Flag] problem.
    // [ < P | == P | > P ]
    //
    // Invariants:
    // 1) a[i] <  P  (left  < i < less)
    // 2) a[i] == P  (less  ≤ i < k)
    // 3) a[i] >  P  (great < i < right)
    //
    // [ |  < P  |  == P  |  ???  |  > P  | ]
    //  ↑         ↑        ↑     ↑         ↑
    //  left      less     k     great     right
    
    __DNF(&a, &less, &great) { cmp($0, P1) }
  } else {
    // If P1 != P2, partition into 3 parts.
    // a[i] < P1, P1 <= a[i] <= P2, a[i] > P2
    //
    // Invariants:
    // 1) a[i] < P1       (left  < i < less)
    // 2) P1 ≤ a[i] ≤ P2  (less  ≤ i < k)
    // 3) P2 < a[i]       (great < i < right)
    //
    // [ | < P1 | >= P1 && <= P2 |  ???  | > P2 | ]
    //  ↑        ↑                ↑     ↑        ↑
    //  left     less             k     great    right
    
    let ltP1 = { isOrderedBefore($0, P1) }
    let gtP2 = { isOrderedBefore(P2, $0) }
    __partition3(&a, &less, &great, ltP1, gtP2)
  }
  
  // Move pivots back into their final positions by swapping both ends.
  (a[left],  a[less  - 1]) = (a[less  - 1], P1)
  (a[right], a[great + 1]) = (a[great + 1], P2)
  
  // Array is now partitioned into 3 parts
  // [ < P1 | >= P1 && <= P2 | > P2 ]
  //
  // Recursively sort left and right partitions
  // up to index (less - 1) since a[less  - 1] == P1
  dualPivotQuickSort(&a, left..<(less - 1), isOrderedBefore) // < P1
  
  // from index (great + 2) since a[great + 1] == P2
  dualPivotQuickSort(&a, (great + 2)..<(right + 1), isOrderedBefore) // > P2
  
  // If P1 == P2, sorting is done because
  // all elements in the middle partition are equal to the pivot.
  // [ < P | == P | > P ]
  if pivotsEqual { return }
  
  // Optimization taken from Dart implementation.
  // If the middle partition is more than 2/3 of the list,
  // remove the pivot elements from the range for the recursive call.
  if (less < idx1 && great > idx5) {
    // Shrink the middle partition by partitioning into 3 parts.
    // a[i] == P1, P1 < a[i] < P2, a[i] == P2
    //
    // Invariants:
    // 1) a[i] == P1      (i < less)
    // 2) P1 < a[i] < P2  (less ≤ i < k)
    // 3) P2 == a[i]      (i < great)
    //
    // | == P1 | > P1 && < P2 |  ???  | == P2 |
    //          ↑              ↑     ↑
    //          less           k     great
    let isP1 = { cmp($0, P1) == 0 }, isP2 = { cmp(P2, $0) == 0 }
    
    while isP1(a[less])  { less++  }
    while isP2(a[great]) { great-- }
    
    __partition3(&a, &less, &great, isP1, isP2) // | >  P1 && <  P2 |
  }
  
  // Recursively sort the middle partition
  // | >= P1 && <= P2 | or | >  P1 && <  P2 |, if optimized
  dualPivotQuickSort(&a, less..<(great + 1), isOrderedBefore)
}

private let _InsertionSortThreshold = 32



// f = compare(x, P)
private func __DNF<T>(inout a: [T], inout L: Int, inout R: Int, f: (T)->Int) {
  // Invariants:
  // 1) f(a[i]) <  0, where i < L
  // 2) f(a[i]) == 0, where L ≤ i < k
  // 3) f(a[i]) >  0, where R < i
  for var k = L; k <= R; k++ {
    let x = a[k]
    let c = f(x)
    if c == 0 { continue }
    
    if c < 0 {
      if k != L {
        a[k] = a[L]
        a[L] = x
      }
      L++
      continue
    }
    
    while true {
      let y = a[R]
      let cy = f(y)
      if cy > 0 { R--; continue }
      
      if cy < 0 {     // Triple exchange
        a[k]   = a[L] // 2 3 1
        a[L++] = y    //  \ \
        a[R--] = x    // 1 2 3
      } else {
        a[k]   = y
        a[R--] = x
      }
      break
    }
  }
}


// Partition into 3 parts using 2 functions which shouldn't overlap.
private func __partition3<T>(inout a: [T], inout L: Int, inout R: Int, f: (T)->Bool, g: (T)->Bool) {
  // Invariants:
  // 1) f(a[i]),              where i < L
  // 2) !f(a[i]) && !g(a[i]), where L ≤ i < k
  // 3) g(a[i]),              where R < i
  // [ | f(x) | !f(x) && !f(g) |  ???  | g(x) | ]
  //  ↑        ↑                ↑     ↑        ↑
  //  left     less             k     great    right
  for var k = L; k <= R; k++ {
    let x = a[k]
    if f(x) {
      if k != L {
        a[k] = a[L]
        a[L] = x
      }
      L++
      continue
    }
    
    if !g(x) { continue }
    
    while true {
      let y = a[R]
      if g(y) {
        if --R < k { break }
        continue
      }
      
      if f(y) {       // Triple exchange
        a[k]   = a[L] // 2 3 1
        a[L++] = y    //  \ \
        a[R--] = x    // 1 2 3 
      } else {
        a[k]   = y
        a[R--] = x
      }
      break
    }
  }
}


// MARK: - References
// - [Dart implementation] : https://github.com/dart-lang/bleeding_edge/blob/master/dart/sdk/lib/internal/sort.dart
// - [DNF] : http://en.wikipedia.org/wiki/Dutch_national_flag_problem
//
// http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
// > Description
// > -----------
// > The classical Quicksort algorithm uses the following scheme:
// > 
// > 1. Pick an element P, called a pivot, from the array.
// > 2. Reorder the array so that all elements, which are less than
// >    the pivot, come before the pivot and all elements greater than
// >    the pivot come after it (equal values can go either way). After
// >    this partitioning, the pivot element is in its final position.
// > 3. Recursively sort the sub-array of lesser elements and the
// >    sub-array of greater elements.
// > 
// > The invariant of classical Quicksort is:
// > 
// > [ <= p | >= p ]
// > 
// > There are several modifications of the schema:
// > 
// > [ < p | = p | > p ]  or  [ = p | < p | > p | = p ]
// > 
// > But all of them use *one* pivot.
// > 
// > The new Dual-Pivot Quicksort uses *two* pivots elements in this manner:
// > 
// > 1. Pick an elements P1, P2, called pivots from the array.
// > 2. Assume that P1 <= P2, otherwise swap it.
// > 3. Reorder the array into three parts: those less than the smaller
// >    pivot, those larger than the larger pivot, and in between are
// >    those elements between (or equal to) the two pivots.
// > 4. Recursively sort the sub-arrays.
// > 
// > The invariant of the Dual-Pivot Quicksort is:
// > 
// > [ < P1 | P1 <= & <= P2 } > P2 ]
// > 
// > The new Quicksort is faster than current implementation of Quicksort
// > in JDK (L. Bentley and M. Douglas McIlroy) and classical Quicksort.