Quicksort written in Swift 3.0

quicksorted.swift

import Foundation

extension Array {
	public func partition(condition: (Element) -> Bool) -> (trueList: [Element], falseList: [Element]) {
		return self.reduce(([], [])) {
			condition($1) ? ($0.0 + [$1], $0.1) : ($0.0, $0.1 + [$1])
		}
	}
}

extension Array where Element : Comparable {
	public func quicksorted(isOrderedBefore: (Element, Element) -> Bool) -> [Element] {
		return self
			.index { self.first! != $0 }
			.map { isOrderedBefore(self.first!, self[$0]) ? self[$0] : self.first! }
			.map { pivot in self.partition { isOrderedBefore($0, pivot) } }
			.map { left, right in left.quicksorted(isOrderedBefore: isOrderedBefore) + right.quicksorted(isOrderedBefore: isOrderedBefore) }
			?? self
	}

	public mutating func quicksort(isOrderedBefore: (Element, Element) -> Bool) {
		if var i = self.index(where: { self.first! != $0 }).map({ isOrderedBefore(self.first!, self[$0]) ? $0 : self.startIndex }) {
			let pivot = self[i]
			for j in self.index(after: i)..<self.endIndex {
				if isOrderedBefore(self[j], pivot) {
					swap(&self[i], &self[j])
					i = self.index(after: i)
				}
			}
			self[self.startIndex..<i].quicksort(isOrderedBefore: isOrderedBefore)
			self[i..<self.endIndex].quicksort(isOrderedBefore: isOrderedBefore)
		}
	}
}

extension ArraySlice where Element : Comparable {
	public mutating func quicksort(isOrderedBefore: (Element, Element) -> Bool) {
		if var i = self.index(where: { self.first! != $0 }).map({ isOrderedBefore(self.first!, self[$0]) ? $0 : self.startIndex }) {
			let pivot = self[i]
			for j in self.index(after: i)..<self.endIndex {
				if isOrderedBefore(self[j], pivot) {
					swap(&self[i], &self[j])
					i = self.index(after: i)
				}
			}
			self[self.startIndex..<i].quicksort(isOrderedBefore: isOrderedBefore)
			self[i..<self.endIndex].quicksort(isOrderedBefore: isOrderedBefore)
		}
	}
}

let array = [10, 10, 3, 2, 5, 4, 1, 7, 11, 8]

print("sorted:")
var start = NSDate()
print(array.sorted(isOrderedBefore: >))
print(NSDate().timeIntervalSince(start))

print("quicksorted:")
start = NSDate()
print(array.quicksorted(isOrderedBefore: >))
print(NSDate().timeIntervalSince(start))

var array2 = array
print("sort:")
start = NSDate()
array2.sort(isOrderedBefore: >)
print(array2)
print(NSDate().timeIntervalSince(start))

array2 = array
print("quicksort:")
start = NSDate()
array2.quicksort(isOrderedBefore: >)
print(array2)
print(NSDate().timeIntervalSince(start))