binary_counter.swift

struct BinaryCounter {
    private init() {}
    
    static func add<C: MutableCollection>(
        counter: inout C,
        x: C.Element,
        zero: C.Element,
        operation op: (C.Element, C.Element) -> C.Element
    ) -> C.Element where C.Element: Equatable {
        
        var i = counter.startIndex
        let end = counter.endIndex
        
        var carry = x
        while i != end {
            if counter[i] == zero {
                counter[i] = carry
                return zero
            }
            
            carry = op(counter[i], carry)
            counter[i] = zero
            i = counter.index(after: i)
        }
        
        return carry
    }
    
    static func reduce<C: MutableCollection>(
        counter: inout C,
        zero: C.Element,
        operation op: (C.Element, C.Element) -> C.Element
    ) -> C.Element where C.Element: Equatable {
        
        var i = counter.startIndex
        let end = counter.endIndex
        
        // find first non-zero
        while i != end && counter[i] == zero {
            i = counter.index(after: i)
        }
        
        if i == end {
            return zero
        }
        
        var x = counter[i]
        i = counter.index(after: i)
        assert(x != zero)

        while i != end {
            if counter[i] != zero {
                x = op(x, counter[i])
            }
            i = counter.index(after: i)
        }
        
        return x
    }
}

extension Sequence where Element: Equatable {
    func balancedFold(
        zero: Element,
        operation op: (Element, Element) -> Element
    ) -> Element{
        var counter = Array(repeating: zero, count: 32)
        
        for x in self {
            let carry = BinaryCounter.add(counter: &counter,
                                          x: x,
                                          zero: zero,
                                          operation: op)
            
            assert(carry == zero, "reduced too many things")
        }
 
        return BinaryCounter.reduce(counter: &counter,
                                    zero: zero,
                                    operation: op)
    }
}


// Application

print([1.0, 2.0, 3.0, 5.0].balancedFold(zero: 0.0, operation: +))

print(MergeSort.sort([1, 3, 7, 2, -4, 8, 20, -6, 8]))




struct MergeSort {
    static func mergeSorted<T>(
        _ a: [T],
        _ b: [T]
    ) -> [T] where T: Comparable  {
        var i = a.startIndex
        var j  = b.startIndex
        
        var out: [T] = []
        
        while i != a.endIndex && j != b.endIndex {
            if b[j] < a[i] {
                out.append(b[j])
                j = a.index(after: j)
            } else {
                out.append(a[i])
                i = a.index(after: i)
            }
        }
        
        if j != a.endIndex {
            out.append(contentsOf: b.suffix(from: j))
        } else {
            out.append(contentsOf: a.suffix(from: i))
        }
        
        return out
    }
    
    static func sort<S: Sequence>(
        _ items: S
    ) -> [S.Element] where S.Element: Comparable {
        
        let singletons: [[S.Element]] = items.map { [$0] }
        let zero: [S.Element] = []
        
        return singletons.balancedFold(zero: zero, operation: mergeSorted)
    }
}