Linked List Quick Sort.swift

final class Node<T>: Sequence {
    let value: T
    var next: Node<T>?
    
    init(_ value: T, next: Node<T>?) {
        self.value = value
        self.next = next
    }
    
    func makeIterator() -> List<T> {
        return List(head: self)
    }
}

struct List<T> : IteratorProtocol {
    var head: Node<T>?
    
    mutating func next() -> Node<T>? {
        let result = head
        head = head?.next
        return result
    }
}

infix operator → : FunctionArrowPrecedence

func →<T>(lhs: T, rhs: T) -> Node<T> {
    return Node(lhs, next: Node(rhs, next: nil))
}

func →<T>(lhs: T, rhs: Node<T>) -> Node<T> {
    return Node(lhs, next: rhs)
}

func →<T>(lhs: Node<T>?, rhs: Node<T>?) -> Node<T>? {
    if let lhs = lhs {
        for node in lhs where node.next == nil || node.next === rhs {
            node.next = rhs
            break
        }
        
        return lhs
    }
    
    return rhs
}

extension Node where T : Comparable, T : CustomStringConvertible {
    func quicksort() -> Node {
        guard let _ = self.next else {
            return self
        }
        
        let (less, more) = self.bifurcate { $0.value < self.value }
        
        return (less?.quicksort() → more?.quicksort()) ?? self
    }
    
    func bifurcate(_ predicate: (Node) -> Bool) -> (Node?, Node?) {
        var (left, right) : (Node?, Node?) = (nil, nil)
        
        for node in self {
            if predicate(node) {
                node.next = left
                left = node
            } else {
                node.next = right
                right = node
            }
        }
        
        return (left, right)
    }
}

for l in (7 → 9 → 3 → 12 → 5 → 1 → 2).quicksort() {
    print(l.value)
}