quick_sort_dual_pivot.swift

// Main idea is to choose two privot elements(lesser pviot and greater pivot) and then divide array in 3 parts:
// 1 part - elements < lesser pviot
// 2 part - elements > lesser pviot && elements < greater pivot
// 3 part - elements >  greater pivot
// and then recursievly sort these parts

extension MutableCollectionType where Self.Generator.Element: Comparable, Self.Index: RandomAccessIndexType {
    
    mutating func swap(src src: Self.Index, dest: Self.Index) {
        let tmp = self[dest]
        self[dest] = self[src]
        self[src] = tmp
    }
    
    
    mutating func quicksort() {
        if self.count < 2 {
            return
        }
    
        quicksort(lo: startIndex, hi: endIndex.advancedBy(-1))
    }
    
    private mutating func quicksort(lo lo: Self.Index, hi: Self.Index) {
        if (lo >= hi) {
            return
        }
        
        let (lesserPivot, greaterPivot) = partition(lo: lo, hi: hi)
        
        quicksort(lo: lo, hi: lesserPivot.advancedBy(-1)) // sort part which < than lesser pivot
        quicksort(lo: lesserPivot.advancedBy(1), hi: greaterPivot.advancedBy(-1)) // part which > lesser pivot && < great pivot
        quicksort(lo: greaterPivot.advancedBy(1), hi: hi) // sort part which > than greater pivot
    }
    
    
    private mutating func partition(lo lo: Self.Index, hi: Self.Index) -> (Self.Index, Self.Index) {
        if self[hi] < self[lo] {
            swap(src: hi, dest: lo)
        }
        
        var start = lo.advancedBy(1)
        var l = start
        var end = hi.advancedBy(-1)
        
        while start <= end {
            if self[start] < self[lo] { // move elements < lesser pivot to start of the collection
                swap(src: start, dest: l)
                l = l.advancedBy(1)
            } else if self[start] > self[hi] {  // move elements > greater pivot to end of the collection
                if start < end && self[end] > self[hi] { //skip elements > greater pivot
                    end = end.advancedBy(-1)
                }
                swap(src: start, dest: end)
                end = end.advancedBy(-1)
                
                if self[start] < self[lo] { // if new elemets appears < lesser pivot move it accordingly
                    swap(src: start, dest: l)
                    l = l.advancedBy(1)
                }
            }
            
            start = start.advancedBy(1)
        }
        
        swap(src: lo, dest: l.advancedBy(-1)) // move lesser pivot element just after last element that < lesser pivot
        swap(src: hi, dest: end.advancedBy(1)) //  move greater pivot element just before first element that > greater pivot
        
        return (lo: l.advancedBy(-1), hi: end.advancedBy(1)) // return new pivots position
    }
}