Don't know where I'm messing up in the sort

Using Swift
1

I'm trying this in a playground:

extension MutableCollection {
    public mutating func stableSort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
        let end = endIndex
        var sortEnd = try sortedPrefix(by: areInIncreasingOrder).endIndex
        while sortEnd < end {
            let nextEnd = try self[sortEnd...].sortedPrefix(by: areInIncreasingOrder).endIndex
            try self[..<nextEnd].mergeSortedPartitions(around: sortEnd, by: areInIncreasingOrder)
            assert(try! self[..<nextEnd].sortedPrefix(by: areInIncreasingOrder).endIndex == nextEnd)
            sortEnd = nextEnd
        }
    }
}

extension MutableCollection where Element: Comparable {
    @inlinable
    public mutating func stableSort() {
        stableSort(by: <)
    }
}

var c = Array<Int>()
c.reserveCapacity(100)
for _ in 0..<100 {
    c.append(Int.random(in: -50..<50))
}
c
c.stableSort()

The array looks OK for the first quarter of it, then I see unsorted elements, which triggers the assert I added. I don't know where I messed up. I think the sort is correct. Of course, I also think the building up methods are correct too.

extension Collection {
    public func sortedPrefix(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> SubSequence {
        let end = endIndex
        var first = startIndex
        guard var second = index(first, offsetBy: +1, limitedBy: end) else {
            return self[first...]
        }

        while second < end {
            guard try !areInIncreasingOrder(self[second], self[first]) else {
                break
            }

            first = second
            formIndex(after: &second)
        }
        return self[..<second]
    }
}
extension MutableCollection {
    public mutating func swapPartitions(around pivot: Index) -> Index {
        let start = startIndex, end = endIndex
        guard start < pivot else { return end }
        guard pivot < end else { return start }

        var firstMarker = start, secondMarker = pivot
        while firstMarker < pivot, secondMarker < end {
            swapAt(firstMarker, secondMarker)
            formIndex(after: &firstMarker)
            formIndex(after: &secondMarker)
        }
        assert(firstMarker == pivot || secondMarker == end)

        if firstMarker < pivot {
            _ = self[firstMarker...].swapPartitions(around: pivot)
            return firstMarker
        } else if secondMarker < end {
            return self[pivot...].swapPartitions(around: secondMarker)
        }
        return pivot

        // To-Do: Make an iterative version.
    }

    public mutating func mergeSortedPartitions(around pivot: Index, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
        // Don't need to merge empty partitions.
        let end = endIndex
        guard pivot < end else { return }

        // Segregate any elements of the first partition that would be within
        // the second.
        let midValue = self[pivot]
        guard let greaterInFirst = try self[..<pivot].firstIndex(where: {
            try areInIncreasingOrder(midValue, $0)
        }) else {
            // First partition already completely less than the second.
            // (Or the first partition is empty.)
            return
        }

        // Segregate the elements of the second partition that would be outside
        // any moved parts of the first.
        let insertionValue = self[greaterInFirst]
        let notLessInSecond = try self[pivot...].firstIndex(where: {
            try !areInIncreasingOrder($0, insertionValue)
        }) ?? end
        self[greaterInFirst..<notLessInSecond].swapPartitions(around: pivot)
    }
}

(I'm building these to showcase something else to the forums.)

2

Your implementation of mergeSortedPartitions has no doc-comments, so the intended semantics are a mystery. Its behavior does not, however, match its name:

var a = [0, 2, 4, 1, 3]
let i = a.sortedPrefix(by: <).endIndex    // 3
print(a[i])                               // 1
a.mergeSortedPartitions(around: i, by: <) // [0, 1, 2, 4, 3]
3

I took out the docs to save space.

/// Assuming both partitions around the given index are sorted according to
/// the given predicate, rearrange the whole collection to be sorted along
/// that predicate.
///
/// The predicate must be a strict weak ordering over the elements.
///
/// The sort is stable; equivalent elements from the same partition keep
/// their relative order.  Equivalent elements from the first partition are
/// placed before those from the second partition.
///
/// - Precondition: `pivot` is a valid index of the collection.
///
/// - Parameter pivot: The start index for the second partition (and the
///   past-the-end index for the first partition.)
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
///   first argument should be ordered before its second argument;
///   otherwise, `false`.
///
/// - Complexity: ???

But I can see that my swapping doesn't handle elements from the first partition with values that are greater than any value from the second partition.

4

This seems to work, but I haven't figured out the complexity of any of these (besides sortedPrefix(by:).

extension MutableCollection {

    /// Assuming both partitions around the given index are sorted according to
    /// the given predicate, rearrange the whole collection to be sorted along
    /// that predicate.
    ///
    /// The predicate must be a strict weak ordering over the elements.
    ///
    /// The sort is stable; equivalent elements from the same partition keep
    /// their relative order.  Equivalent elements from the first partition are
    /// placed before those from the second partition.
    ///
    /// - Precondition: `pivot` is a valid index of the collection.
    ///
    /// - Parameter pivot: The start index for the second partition (and the
    ///   past-the-end index for the first partition.)
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    ///
    /// - Complexity: ???
    public mutating func mergeSortedPartitions(around pivot: Index, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
        // Don't need to merge empty partitions.
        let end = endIndex
        guard pivot < end else { return }

        // Segregate any elements of the first partition that would be within
        // the second.
        let midValue = self[pivot]
        guard let greaterInFirst = try self[..<pivot].firstIndex(where: {
            try areInIncreasingOrder(midValue, $0)
        }) else {
            // First partition already completely less than the second.
            // (Or the first partition is empty.)
            return
        }

        // Segregate the elements of the second partition that would be outside
        // any moved parts of the first.
        let insertionValue = self[greaterInFirst]
        let notLessInSecond = try self[pivot...].firstIndex(where: {
            try !areInIncreasingOrder($0, insertionValue)
        }) ?? end
        let newFirstSuffix = self[greaterInFirst..<notLessInSecond].swapPartitions(around: pivot)
        try self[newFirstSuffix...].mergeSortedPartitions(around: notLessInSecond, by: areInIncreasingOrder)

        // To-Do: Make an iterative version.
    }

}

The result took a couple seconds to chug out.

5

Looks a lot like Insertion Sort.

6

Which is O(n^2) on average. The point of this exercise is to get the collection sorted so I can do a permutation sequence on it. Maybe it’s better to use the existing Sequence.sorted to an Array and copy the sorted elements back to a copy of the mutable collection I’ll be keeping. The sort I had minimizes space and can be used for non-random-access collections, but the trade-off may not be worth it.