test/Prototypes/IntroSort.swift - third_party/swift - Git at Google

 //===--- IntroSort.swift --------------------------------------*- swift -*-===//
 //
 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2018 Apple Inc. and the Swift project authors
 // Licensed under Apache License v2.0 with Runtime Library Exception
 //
 // See https://swift.org/LICENSE.txt for license information
 // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
 //
 //===----------------------------------------------------------------------===//
 // RUN: %empty-directory(%t)
 // RUN: %target-build-swift -g -Onone -DUSE_STDLIBUNITTEST %s -o %t/a.out
 // RUN: %target-codesign %t/a.out
 // RUN: %target-run %t/a.out
 // REQUIRES: executable_test

 // Note: This introsort was the standard library's sort algorithm until Swift 5.

 import Swift
 import StdlibUnittest

 extension MutableCollection {
   /// Sorts the elements at `elements[a]`, `elements[b]`, and `elements[c]`.
   /// Stable.
   ///
   /// The indices passed as `a`, `b`, and `c` do not need to be consecutive, but
   /// must be in strict increasing order.
   ///
   /// - Precondition: `a < b && b < c`
   /// - Postcondition: `self[a] <= self[b] && self[b] <= self[c]`
   @inlinable
   public // @testable
   mutating func _sort3(
     _ a: Index, _ b: Index, _ c: Index,
     by areInIncreasingOrder: (Element, Element) throws -> Bool
   ) rethrows {
     // There are thirteen possible permutations for the original ordering of
     // the elements at indices `a`, `b`, and `c`. The comments in the code below
     // show the relative ordering of the three elements using a three-digit
     // number as shorthand for the position and comparative relationship of
     // each element. For example, "312" indicates that the element at `a` is the
     // largest of the three, the element at `b` is the smallest, and the element
     // at `c` is the median. This hypothetical input array has a 312 ordering for
     // `a`, `b`, and `c`:
     //
     //      [ 7, 4, 3, 9, 2, 0, 3, 7, 6, 5 ]
     //        ^              ^           ^
     //        a              b           c
     //
     // - If each of the three elements is distinct, they could be ordered as any
     //   of the permutations of 1, 2, and 3: 123, 132, 213, 231, 312, or 321.
     // - If two elements are equivalent and one is distinct, they could be
     //   ordered as any permutation of 1, 1, and 2 or 1, 2, and 2: 112, 121, 211,
     //   122, 212, or 221.
     // - If all three elements are equivalent, they are already in order: 111.

     switch try (areInIncreasingOrder(self[b], self[a]),
                 areInIncreasingOrder(self[c], self[b])) {
     case (false, false):
       // 0 swaps: 123, 112, 122, 111
       break

     case (true, true):
       // 1 swap: 321
       // swap(a, c): 312->123
       swapAt(a, c)

     case (true, false):
       // 1 swap: 213, 212 --- 2 swaps: 312, 211
       // swap(a, b): 213->123, 212->122, 312->132, 211->121
       swapAt(a, b)

       if try areInIncreasingOrder(self[c], self[b]) {
         // 132 (started as 312), 121 (started as 211)
         // swap(b, c): 132->123, 121->112
         swapAt(b, c)
       }

     case (false, true):
       // 1 swap: 132, 121 --- 2 swaps: 231, 221
       // swap(b, c): 132->123, 121->112, 231->213, 221->212
       swapAt(b, c)

       if try areInIncreasingOrder(self[b], self[a]) {
         // 213 (started as 231), 212 (started as 221)
         // swap(a, b): 213->123, 212->122
         swapAt(a, b)
       }
     }
   }
 }

 extension MutableCollection where Self: RandomAccessCollection {
   /// Reorders the collection and returns an index `p` such that every element
   /// in `range.lowerBound..<p` is less than every element in
   /// `p..<range.upperBound`.
   ///
   /// - Precondition: The count of `range` must be >= 3 i.e.
   ///   `distance(from: range.lowerBound, to: range.upperBound) >= 3`
   @inlinable
   internal mutating func _partition(
     within range: Range<Index>,
     by areInIncreasingOrder: (Element, Element) throws -> Bool
   ) rethrows -> Index {
     var lo = range.lowerBound
     var hi = index(before: range.upperBound)

     // Sort the first, middle, and last elements, then use the middle value
     // as the pivot for the partition.
     let half = distance(from: lo, to: hi) / 2
     let mid = index(lo, offsetBy: half)
     try _sort3(lo, mid, hi, by: areInIncreasingOrder)

     // FIXME: Stashing the pivot element instead of using the index won't work
     // for move-only types.
     let pivot = self[mid]

     // Loop invariants:
     // * lo < hi
     // * self[i] < pivot, for i in range.lowerBound..<lo
     // * pivot <= self[i] for i in hi..<range.upperBound
     Loop: while true {
       FindLo: do {
         formIndex(after: &lo)
         while lo != hi {
           if try !areInIncreasingOrder(self[lo], pivot) { break FindLo }
           formIndex(after: &lo)
         }
         break Loop
       }

       FindHi: do {
         formIndex(before: &hi)
         while hi != lo {
           if try areInIncreasingOrder(self[hi], pivot) { break FindHi }
           formIndex(before: &hi)
         }
         break Loop
       }

       swapAt(lo, hi)
     }

     return lo
   }

   @inlinable
   public // @testable
   mutating func _introSort(
     within range: Range<Index>,
     by areInIncreasingOrder: (Element, Element) throws -> Bool
   ) rethrows {

     let n = distance(from: range.lowerBound, to: range.upperBound)
     guard n > 1 else { return }

     // Set max recursion depth to 2*floor(log(N)), as suggested in the introsort
     // paper: http://www.cs.rpi.edu/~musser/gp/introsort.ps
     let depthLimit = 2 * n._binaryLogarithm()
     try _introSortImpl(
       within: range,
       by: areInIncreasingOrder,
       depthLimit: depthLimit)
   }

   @inlinable
   internal mutating func _introSortImpl(
     within range: Range<Index>,
     by areInIncreasingOrder: (Element, Element) throws -> Bool,
     depthLimit: Int
   ) rethrows {

     // Insertion sort is better at handling smaller regions.
     if distance(from: range.lowerBound, to: range.upperBound) < 20 {
       try _insertionSort(within: range, by: areInIncreasingOrder)
     } else if depthLimit == 0 {
       try _heapSort(within: range, by: areInIncreasingOrder)
     } else {
       // Partition and sort.
       // We don't check the depthLimit variable for underflow because this
       // variable is always greater than zero (see check above).
       let partIdx = try _partition(within: range, by: areInIncreasingOrder)
       try _introSortImpl(
         within: range.lowerBound..<partIdx,
         by: areInIncreasingOrder,
         depthLimit: depthLimit &- 1)
       try _introSortImpl(
         within: partIdx..<range.upperBound,
         by: areInIncreasingOrder,
         depthLimit: depthLimit &- 1)
     }
   }

   @inlinable
   internal mutating func _siftDown(
     _ idx: Index,
     within range: Range<Index>,
     by areInIncreasingOrder: (Element, Element) throws -> Bool
   ) rethrows {
     var idx = idx
     var countToIndex = distance(from: range.lowerBound, to: idx)
     var countFromIndex = distance(from: idx, to: range.upperBound)
     // Check if left child is within bounds. If not, stop iterating, because
     // there are no children of the given node in the heap.
     while countToIndex + 1 < countFromIndex {
       let left = index(idx, offsetBy: countToIndex + 1)
       var largest = idx
       if try areInIncreasingOrder(self[largest], self[left]) {
         largest = left
       }
       // Check if right child is also within bounds before trying to examine it.
       if countToIndex + 2 < countFromIndex {
         let right = index(after: left)
         if try areInIncreasingOrder(self[largest], self[right]) {
           largest = right
         }
       }
       // If a child is bigger than the current node, swap them and continue
       // sifting down.
       if largest != idx {
         swapAt(idx, largest)
         idx = largest
         countToIndex = distance(from: range.lowerBound, to: idx)
         countFromIndex = distance(from: idx, to: range.upperBound)
       } else {
         break
       }
     }
   }

   @inlinable
   internal mutating func _heapify(
     within range: Range<Index>,
     by areInIncreasingOrder: (Element, Element) throws -> Bool
   ) rethrows {
     // Here we build a heap starting from the lowest nodes and moving to the
     // root. On every step we sift down the current node to obey the max-heap
     // property:
     //   parent >= max(leftChild, rightChild)
     //
     // We skip the rightmost half of the array, because these nodes don't have
     // any children.
     let root = range.lowerBound
     let half = distance(from: range.lowerBound, to: range.upperBound) / 2
     var node = index(root, offsetBy: half)

     while node != root {
       formIndex(before: &node)
       try _siftDown(node, within: range, by: areInIncreasingOrder)
     }
   }

   @inlinable
   public // @testable
   mutating func _heapSort(
     within range: Range<Index>,
     by areInIncreasingOrder: (Element, Element) throws -> Bool
   ) rethrows {
     var hi = range.upperBound
     let lo = range.lowerBound
     try _heapify(within: range, by: areInIncreasingOrder)
     formIndex(before: &hi)
     while hi != lo {
       swapAt(lo, hi)
       try _siftDown(lo, within: lo..<hi, by: areInIncreasingOrder)
       formIndex(before: &hi)
     }
   }
 }

 //===--- Tests ------------------------------------------------------------===//
 //===----------------------------------------------------------------------===//

 var suite = TestSuite("IntroSort")

 // The routine is based on http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
 func makeQSortKiller(_ len: Int) -> [Int] {
   var candidate: Int = 0
   var keys = [Int: Int]()
   func Compare(_ x: Int, y : Int) -> Bool {
     if keys[x] == nil && keys[y] == nil {
       if (x == candidate) {
         keys[x] = keys.count
       } else {
         keys[y] = keys.count
       }
     }
     if keys[x] == nil {
       candidate = x
       return true
     }
     if keys[y] == nil {
       candidate = y
       return false
     }
     return keys[x]! > keys[y]!
   }

   var ary = [Int](repeating: 0, count: len)
   var ret = [Int](repeating: 0, count: len)
   for i in 0..<len { ary[i] = i }
   ary = ary.sorted(by: Compare)
   for i in 0..<len {
     ret[ary[i]] = i
   }
   return ret
 }

 suite.test("sorted/complexity") {
   var ary: [Int] = []

   // Check performance of sorting an array of repeating values.
   var comparisons_100 = 0
   ary = Array(repeating: 0, count: 100)
   ary._introSort(within: 0..<ary.count) { comparisons_100 += 1; return $0 < $1 }
   var comparisons_1000 = 0
   ary = Array(repeating: 0, count: 1000)
   ary._introSort(within: 0..<ary.count) { comparisons_1000 += 1; return $0 < $1 }
   expectTrue(comparisons_1000/comparisons_100 < 20)

   // Try to construct 'bad' case for quicksort, on which the algorithm
   // goes quadratic.
   comparisons_100 = 0
   ary = makeQSortKiller(100)
   ary._introSort(within: 0..<ary.count) { comparisons_100 += 1; return $0 < $1 }
   comparisons_1000 = 0
   ary = makeQSortKiller(1000)
   ary._introSort(within: 0..<ary.count) { comparisons_1000 += 1; return $0 < $1 }
   expectTrue(comparisons_1000/comparisons_100 < 20)
 }

 suite.test("sort3/simple")
   .forEach(in: [
     [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
   ]) {
     var input = $0
     input._sort3(0, 1, 2, by: <)
     expectEqual([1, 2, 3], input)
 }

 func isSorted<T>(_ a: [T], by areInIncreasingOrder: (T, T) -> Bool) -> Bool {
   return !zip(a.dropFirst(), a).contains(where: areInIncreasingOrder)
 }

 suite.test("sort3/stable")
   .forEach(in: [
     [1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 2, 2], [2, 1, 2], [2, 2, 1], [1, 1, 1]
   ]) {
     // decorate with offset, but sort by value
     var input = Array($0.enumerated())
     input._sort3(0, 1, 2) { $0.element < $1.element }
     // offsets should still be ordered for equal values
     expectTrue(isSorted(input) {
       if $0.element == $1.element {
         return $0.offset < $1.offset
       }
       return $0.element < $1.element
     })
 }

 suite.test("heapSort") {
   // Generates the next permutation of `num` as a binary integer, using long
   // arithmetics approach.
   //
   // - Precondition: All values in `num` are either 0 or 1.
   func addOne(to num: [Int]) -> [Int] {
     // `num` represents a binary integer. To add one, we toggle any bits until
     // we've set a clear bit.
     var num = num
     for i in num.indices {
       if num[i] == 1 {
         num[i] = 0
       } else {
         num[i] = 1
         break
       }
     }
     return num
   }

   // Test binary number size.
   let numberLength = 11
   var binaryNumber = Array(repeating: 0, count: numberLength)

   // We are testing sort on all permutations off 0-1s of size `numberLength`
   // except the all 1's case (its equals to all 0's case).
   while !binaryNumber.allSatisfy({ $0 == 1 }) {
     var buffer = binaryNumber
     buffer._heapSort(within: buffer.startIndex..<buffer.endIndex, by: <)
     expectTrue(isSorted(buffer, by: <))
     binaryNumber = addOne(to: binaryNumber)
   }
 }

 runAllTests()
	//===--- IntroSort.swift --------------------------------------- swift --===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2018 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See https://swift.org/LICENSE.txt for license information
	// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//
	// RUN: %empty-directory(%t)
	// RUN: %target-build-swift -g -Onone -DUSE_STDLIBUNITTEST %s -o %t/a.out
	// RUN: %target-codesign %t/a.out
	// RUN: %target-run %t/a.out
	// REQUIRES: executable_test

	// Note: This introsort was the standard library's sort algorithm until Swift 5.

	import Swift
	import StdlibUnittest

	extension MutableCollection {
	/// Sorts the elements at `elements[a]`, `elements[b]`, and `elements[c]`.
	/// Stable.
	///
	/// The indices passed as `a`, `b`, and `c` do not need to be consecutive, but
	/// must be in strict increasing order.
	///
	/// - Precondition: `a < b && b < c`
	/// - Postcondition: `self[a] <= self[b] && self[b] <= self[c]`
	@inlinable
	public // @testable
	mutating func _sort3(
	_ a: Index, _ b: Index, _ c: Index,
	by areInIncreasingOrder: (Element, Element) throws -> Bool
	) rethrows {
	// There are thirteen possible permutations for the original ordering of
	// the elements at indices `a`, `b`, and `c`. The comments in the code below
	// show the relative ordering of the three elements using a three-digit
	// number as shorthand for the position and comparative relationship of
	// each element. For example, "312" indicates that the element at `a` is the
	// largest of the three, the element at `b` is the smallest, and the element
	// at `c` is the median. This hypothetical input array has a 312 ordering for
	// `a`, `b`, and `c`:
	//
	// [ 7, 4, 3, 9, 2, 0, 3, 7, 6, 5 ]
	// ^ ^ ^
	// a b c
	//
	// - If each of the three elements is distinct, they could be ordered as any
	// of the permutations of 1, 2, and 3: 123, 132, 213, 231, 312, or 321.
	// - If two elements are equivalent and one is distinct, they could be
	// ordered as any permutation of 1, 1, and 2 or 1, 2, and 2: 112, 121, 211,
	// 122, 212, or 221.
	// - If all three elements are equivalent, they are already in order: 111.

	switch try (areInIncreasingOrder(self[b], self[a]),
	areInIncreasingOrder(self[c], self[b])) {
	case (false, false):
	// 0 swaps: 123, 112, 122, 111
	break

	case (true, true):
	// 1 swap: 321
	// swap(a, c): 312->123
	swapAt(a, c)

	case (true, false):
	// 1 swap: 213, 212 --- 2 swaps: 312, 211
	// swap(a, b): 213->123, 212->122, 312->132, 211->121
	swapAt(a, b)

	if try areInIncreasingOrder(self[c], self[b]) {
	// 132 (started as 312), 121 (started as 211)
	// swap(b, c): 132->123, 121->112
	swapAt(b, c)
	}

	case (false, true):
	// 1 swap: 132, 121 --- 2 swaps: 231, 221
	// swap(b, c): 132->123, 121->112, 231->213, 221->212
	swapAt(b, c)

	if try areInIncreasingOrder(self[b], self[a]) {
	// 213 (started as 231), 212 (started as 221)
	// swap(a, b): 213->123, 212->122
	swapAt(a, b)
	}
	}
	}
	}

	extension MutableCollection where Self: RandomAccessCollection {
	/// Reorders the collection and returns an index `p` such that every element
	/// in `range.lowerBound..<p` is less than every element in
	/// `p..<range.upperBound`.
	///
	/// - Precondition: The count of `range` must be >= 3 i.e.
	/// `distance(from: range.lowerBound, to: range.upperBound) >= 3`
	@inlinable
	internal mutating func _partition(
	within range: Range<Index>,
	by areInIncreasingOrder: (Element, Element) throws -> Bool
	) rethrows -> Index {
	var lo = range.lowerBound
	var hi = index(before: range.upperBound)

	// Sort the first, middle, and last elements, then use the middle value
	// as the pivot for the partition.
	let half = distance(from: lo, to: hi) / 2
	let mid = index(lo, offsetBy: half)
	try _sort3(lo, mid, hi, by: areInIncreasingOrder)

	// FIXME: Stashing the pivot element instead of using the index won't work
	// for move-only types.
	let pivot = self[mid]

	// Loop invariants:
	// * lo < hi
	// * self[i] < pivot, for i in range.lowerBound..<lo
	// * pivot <= self[i] for i in hi..<range.upperBound
	Loop: while true {
	FindLo: do {
	formIndex(after: &lo)
	while lo != hi {
	if try !areInIncreasingOrder(self[lo], pivot) { break FindLo }
	formIndex(after: &lo)
	}
	break Loop
	}

	FindHi: do {
	formIndex(before: &hi)
	while hi != lo {
	if try areInIncreasingOrder(self[hi], pivot) { break FindHi }
	formIndex(before: &hi)
	}
	break Loop
	}

	swapAt(lo, hi)
	}

	return lo
	}

	@inlinable
	public // @testable
	mutating func _introSort(
	within range: Range<Index>,
	by areInIncreasingOrder: (Element, Element) throws -> Bool
	) rethrows {

	let n = distance(from: range.lowerBound, to: range.upperBound)
	guard n > 1 else { return }

	// Set max recursion depth to 2*floor(log(N)), as suggested in the introsort
	// paper: http://www.cs.rpi.edu/~musser/gp/introsort.ps
	let depthLimit = 2 * n._binaryLogarithm()
	try _introSortImpl(
	within: range,
	by: areInIncreasingOrder,
	depthLimit: depthLimit)
	}

	@inlinable
	internal mutating func _introSortImpl(
	within range: Range<Index>,
	by areInIncreasingOrder: (Element, Element) throws -> Bool,
	depthLimit: Int
	) rethrows {

	// Insertion sort is better at handling smaller regions.
	if distance(from: range.lowerBound, to: range.upperBound) < 20 {
	try _insertionSort(within: range, by: areInIncreasingOrder)
	} else if depthLimit == 0 {
	try _heapSort(within: range, by: areInIncreasingOrder)
	} else {
	// Partition and sort.
	// We don't check the depthLimit variable for underflow because this
	// variable is always greater than zero (see check above).
	let partIdx = try _partition(within: range, by: areInIncreasingOrder)
	try _introSortImpl(
	within: range.lowerBound..<partIdx,
	by: areInIncreasingOrder,
	depthLimit: depthLimit &- 1)
	try _introSortImpl(
	within: partIdx..<range.upperBound,
	by: areInIncreasingOrder,
	depthLimit: depthLimit &- 1)
	}
	}

	@inlinable
	internal mutating func _siftDown(
	_ idx: Index,
	within range: Range<Index>,
	by areInIncreasingOrder: (Element, Element) throws -> Bool
	) rethrows {
	var idx = idx
	var countToIndex = distance(from: range.lowerBound, to: idx)
	var countFromIndex = distance(from: idx, to: range.upperBound)
	// Check if left child is within bounds. If not, stop iterating, because
	// there are no children of the given node in the heap.
	while countToIndex + 1 < countFromIndex {
	let left = index(idx, offsetBy: countToIndex + 1)
	var largest = idx
	if try areInIncreasingOrder(self[largest], self[left]) {
	largest = left
	}
	// Check if right child is also within bounds before trying to examine it.
	if countToIndex + 2 < countFromIndex {
	let right = index(after: left)
	if try areInIncreasingOrder(self[largest], self[right]) {
	largest = right
	}
	}
	// If a child is bigger than the current node, swap them and continue
	// sifting down.
	if largest != idx {
	swapAt(idx, largest)
	idx = largest
	countToIndex = distance(from: range.lowerBound, to: idx)
	countFromIndex = distance(from: idx, to: range.upperBound)
	} else {
	break
	}
	}
	}

	@inlinable
	internal mutating func _heapify(
	within range: Range<Index>,
	by areInIncreasingOrder: (Element, Element) throws -> Bool
	) rethrows {
	// Here we build a heap starting from the lowest nodes and moving to the
	// root. On every step we sift down the current node to obey the max-heap
	// property:
	// parent >= max(leftChild, rightChild)
	//
	// We skip the rightmost half of the array, because these nodes don't have
	// any children.
	let root = range.lowerBound
	let half = distance(from: range.lowerBound, to: range.upperBound) / 2
	var node = index(root, offsetBy: half)

	while node != root {
	formIndex(before: &node)
	try _siftDown(node, within: range, by: areInIncreasingOrder)
	}
	}

	@inlinable
	public // @testable
	mutating func _heapSort(
	within range: Range<Index>,
	by areInIncreasingOrder: (Element, Element) throws -> Bool
	) rethrows {
	var hi = range.upperBound
	let lo = range.lowerBound
	try _heapify(within: range, by: areInIncreasingOrder)
	formIndex(before: &hi)
	while hi != lo {
	swapAt(lo, hi)
	try _siftDown(lo, within: lo..<hi, by: areInIncreasingOrder)
	formIndex(before: &hi)
	}
	}
	}

	//===--- Tests ------------------------------------------------------------===//
	//===----------------------------------------------------------------------===//

	var suite = TestSuite("IntroSort")

	// The routine is based on http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
	func makeQSortKiller(_ len: Int) -> [Int] {
	var candidate: Int = 0
	var keys = [Int: Int]()
	func Compare(_ x: Int, y : Int) -> Bool {
	if keys[x] == nil && keys[y] == nil {
	if (x == candidate) {
	keys[x] = keys.count
	} else {
	keys[y] = keys.count
	}
	}
	if keys[x] == nil {
	candidate = x
	return true
	}
	if keys[y] == nil {
	candidate = y
	return false
	}
	return keys[x]! > keys[y]!
	}

	var ary = [Int](repeating: 0, count: len)
	var ret = [Int](repeating: 0, count: len)
	for i in 0..<len { ary[i] = i }
	ary = ary.sorted(by: Compare)
	for i in 0..<len {
	ret[ary[i]] = i
	}
	return ret
	}

	suite.test("sorted/complexity") {
	var ary: [Int] = []

	// Check performance of sorting an array of repeating values.
	var comparisons_100 = 0
	ary = Array(repeating: 0, count: 100)
	ary._introSort(within: 0..<ary.count) { comparisons_100 += 1; return $0 < $1 }
	var comparisons_1000 = 0
	ary = Array(repeating: 0, count: 1000)
	ary._introSort(within: 0..<ary.count) { comparisons_1000 += 1; return $0 < $1 }
	expectTrue(comparisons_1000/comparisons_100 < 20)

	// Try to construct 'bad' case for quicksort, on which the algorithm
	// goes quadratic.
	comparisons_100 = 0
	ary = makeQSortKiller(100)
	ary._introSort(within: 0..<ary.count) { comparisons_100 += 1; return $0 < $1 }
	comparisons_1000 = 0
	ary = makeQSortKiller(1000)
	ary._introSort(within: 0..<ary.count) { comparisons_1000 += 1; return $0 < $1 }
	expectTrue(comparisons_1000/comparisons_100 < 20)
	}

	suite.test("sort3/simple")
	.forEach(in: [
	[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
	]) {
	var input = $0
	input._sort3(0, 1, 2, by: <)
	expectEqual([1, 2, 3], input)
	}

	func isSorted<T>(_ a: [T], by areInIncreasingOrder: (T, T) -> Bool) -> Bool {
	return !zip(a.dropFirst(), a).contains(where: areInIncreasingOrder)
	}

	suite.test("sort3/stable")
	.forEach(in: [
	[1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 2, 2], [2, 1, 2], [2, 2, 1], [1, 1, 1]
	]) {
	// decorate with offset, but sort by value
	var input = Array($0.enumerated())
	input._sort3(0, 1, 2) { $0.element < $1.element }
	// offsets should still be ordered for equal values
	expectTrue(isSorted(input) {
	if $0.element == $1.element {
	return $0.offset < $1.offset
	}
	return $0.element < $1.element
	})
	}

	suite.test("heapSort") {
	// Generates the next permutation of `num` as a binary integer, using long
	// arithmetics approach.
	//
	// - Precondition: All values in `num` are either 0 or 1.
	func addOne(to num: [Int]) -> [Int] {
	// `num` represents a binary integer. To add one, we toggle any bits until
	// we've set a clear bit.
	var num = num
	for i in num.indices {
	if num[i] == 1 {
	num[i] = 0
	} else {
	num[i] = 1
	break
	}
	}
	return num
	}

	// Test binary number size.
	let numberLength = 11
	var binaryNumber = Array(repeating: 0, count: numberLength)

	// We are testing sort on all permutations off 0-1s of size `numberLength`
	// except the all 1's case (its equals to all 0's case).
	while !binaryNumber.allSatisfy({ $0 == 1 }) {
	var buffer = binaryNumber
	buffer._heapSort(within: buffer.startIndex..<buffer.endIndex, by: <)
	expectTrue(isSorted(buffer, by: <))
	binaryNumber = addOne(to: binaryNumber)
	}
	}

	runAllTests()