What order is this sorting method?

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.
        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)?

If you’re getting O(n)... are you sure you’re counting all of the recursion steps?

If the recursion splits the array symetrically, then you have in each level:

  • 1 array
  • 2 (1/2)s of the array
  • 4 (1/4)s
  • 8 (1/8)s
  • ...
  • n (1/n)s of the array

There are log(n) levels, and since each level incurs in O(n) steps, the overall complexity is O(n log(n))

I haven’t read your code (I’m in my tiny phone atm), but that might be what you missed :slightly_smiling_face:

If that really is a merge sort, then the complexity is O(n*logn). (I haven't read your code attentively, but I noticed you call mergeSort only once recursively. Merge sort divides the sequence into two halves, sorts each and then merges them).
The recurrence relation of merge sort is T(n) = 2T(n / 2) + ϴ(n) for the worst case, which via the 2nd case of the master theorem becomes ϴ(nlogn). That is O(n*logn) in average. Never leave out recursions if their depth isn't constant! :wink:

1 Like

The first half is what Wikipedia calls a natural merge sort; a split where the collection is already properly sorted. That’s why only the second half gets a recursive call.