Creates a diff for two sorted arrays that transforms one array into the other. CAUTION: I'm not sure yet whether contents of "changed" are correct in all cases. Please notify me at @manuelmaly if you see any issues.

SortedArrayDiff.swift

import Foundation

extension Array where Element:Equatable {
    typealias ArrayDiffResult = (added: [(Index, Element)], removed: [(Index, Element)], changed: [(Index, Element)])

    // Inspired by: http://stackoverflow.com/q/3476672/458603
    // compare has to return .orderedSame if the identity of the element is the same,
    // even if the element's values have changed.
    func diff(other: Array<Element>, compare: ((Element, Element) -> ComparisonResult), preSorted: Bool) -> ArrayDiffResult {
        
        let areInIncreasingOrder: @noescape (Element, Element) -> Bool = { (a, b) in
            return compare(a, b) == .orderedAscending
        }
        let sortedSelf = preSorted ? self : self.sorted(by: areInIncreasingOrder)
        let sortedOther = preSorted ? other : other.sorted(by: areInIncreasingOrder)
        
        if sortedSelf.count == 0 || sortedOther.count == 0 {
            return (other.enumerated().map({($0, $1)}), self.enumerated().map({($0, $1)}), [])
        }
        
        var selfPointer = 0, otherPointer = 0
        var added = [(Index, Element)](), removed = [(Index, Element)](), changed = [(Index, Element)]()
        
        while selfPointer < self.count && otherPointer < other.count {
            let comparisonResult = compare(self[selfPointer], other[otherPointer])
            
            switch comparisonResult {
            case .orderedAscending:
                removed.append((selfPointer, self[selfPointer]))
                selfPointer += 1
            case .orderedDescending:
                added.append((otherPointer, other[otherPointer]))
                otherPointer += 1
            default:
                if self[selfPointer] != other[otherPointer] {
                    changed.append((selfPointer, self[selfPointer]))
                }
                selfPointer += 1
                otherPointer += 1
            }
        }
        
        
        if otherPointer < other.count {
            let restOfOther = (otherPointer..<other.count).map({ ($0, other[$0]) })
            added.append(contentsOf: restOfOther)
        }
        
        if selfPointer < self.count {
            let restOfSelf = (selfPointer..<self.count).map({ ($0, self[$0]) })
            removed.append(contentsOf: restOfSelf)
        }
        
        return (added, removed, changed)
    }
    
}