Here's an implementation of the merge sort in a protocol extension of a linked-list protocol:
extension PoorlyTransferableCollection {
/// Creates an instance by merging the elements of two other instances, with admission order controlled by a closure.
public init(stealFromAndMerge first: inout Self, and second: inout Self, admitFirstOverSecond body: (Element, Element) throws -> Bool) rethrows {
// Determine the order of insertion.
var firstIndex = first.startIndex, secondIndex = second.startIndex
var chooseFirst = [Bool]()
while firstIndex != first.endIndex, secondIndex != second.endIndex {
chooseFirst.append(try body(first[firstIndex], second[secondIndex]))
first.formIndex(after: &firstIndex)
second.formIndex(after: &secondIndex)
}
// Do the insertions.
self.init()
reserveCapacity(chooseFirst.count)
chooseFirst.forEach {
if $0 {
trade(.afterEnd, with: &first, along: .prefix(upThrough: first.startIndex))
} else {
trade(.afterEnd, with: &second, along: .prefix(upThrough: second.startIndex))
}
}
append(stealingFrom: &first)
append(stealingFrom: &second)
}
/// Detaches and returns a suffix, breaking where the prefix would no longer match a running sort.
public mutating func purgeSuffixMissorted(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Self? {
var lastIncluded = startIndex
for i in indices.dropFirst() {
if try !areInIncreasingOrder(self[lastIncluded], self[i]) {
return truncate(after: lastIncluded)
}
lastIncluded = i
}
return nil
}
/// Sorts the collection in place via storage-shuffling, using the given predicate as the comparison between elements.
public mutating func mergeSort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
// Check if this instance is already sorted.
guard var missortedSuffix = try purgeSuffixMissorted(by: areInIncreasingOrder) else { return }
// Undo the truncation if later steps throw. Or uselessly append an emptied intermediary if nothing threw.
defer { append(stealingFrom: &missortedSuffix) }
// Recursively sort.
try missortedSuffix.mergeSort(by: areInIncreasingOrder)
// Merge. Using the suffix collection as the first argument should make equivalent operands choose the element from this instance first.
var sorted = try Self(stealFromAndMerge: &missortedSuffix, and: &self, admitFirstOverSecond: areInIncreasingOrder)
trade(.all, with: &sorted, along: .all)
}
}
The protocol's core method, trade(_: with: along:), is O(1), along with append(stealingFrom:) and truncate(after:), since all of them just do simple link surgery. The init(stealFromAndMerge: and: admitFirstOverSecond:) and purgeSuffixMissorted(by:) members should be O(n).
I'm wondering about mergeSort(by:). There is a recursive call, but the length call's vector is shorter. The purgeSuffixMissorted step splits the collection in two, and it doesn't look at the second half, while the recursive call only looks at the second half. The merging initializer goes through each halves' elements about once. So I think the complexity should be (O(n/2) + O(n/2)) * 2 == O(2n), or O(n). Or am I doing the calculations wrong and it's actually O(n^2)?
