Sort State University

Stateful sorting algorithms for Swift.

Imagine…

A sorting algorithm is a value type that can be called as a function. Its state represents a specific moment in the execution of the algorithm. Each call will advance the algorithm and produce a step: either a comparison to be answered, or the final sorted output. The comparison will produce the next value of the algorithm when given an answer. The next value of the algorithm can be called to produce the next step, and so on, until the output is produced.

Sort State University brings this dream to life.

• Insertion Sort
• Merge Sort

• Asynchronous sorting
• Sorting visualizations
• Et cetera

The sorting algorithms in this framework are not designed for performance and are not intended to be used for general-purpose implementations.

I knew that "sort" and "state" had to be in the name. It seemed natural and funny to append "university." There is nothing inherently educational about this framework.

var algorithm = MergeSort(input: elements)

The input to an algorithm does not need to conform to Comparable because the answers to the comparisons are supplied by the caller.

A mutable algorithm can be called like a function. The return value is the next step in the algorithm: either a comparison or the final sorted output.

switch algorithm() {
case let .comparison(comparison):
    // Answer the comparison…
case let .finished(output):
    // Handle the sorted output…
}

A comparison is a decision about the inherent order of two elements. The caller is responsible for consistently applying the inherent order to the comparisons. For example, the "inherent order" could be a user's personal preference, so the answer to the comparions would be whichever element the user prefers.

A comparison can be answered directly to produce the next state of the sorting algorithm.

algorithm = comparison(.left)

or

algorithm = comparison(.right)

The answer to a comparison can also be provided to, and mutate, the algorithm directly. Both approaches produce the same result but their calling patterns suit different use cases.

algorithm.answer(.left)

or

algorithm.answer(.right)

The output is a sorted array of elements. Handling this value is an exercise left to the reader.

• iOS 14.0+
• macOS 11.0+
• tvOS 14.0+
• watchOS 7.0+

• Swift 5.3+
• Xcode 12.0+

dependencies: [
    .package(url: "https://github.com/kylehughes/sort-state-university.git", from: "1.0.0"),
]

Documentation is available here.

Generated with jazzy. Hosted by GitHub Pages.

Sort State University is not accepting source contributions at this time. Bug reports will be considered.

This framework is a personal hobby. Feel free to copy pieces, or to fork, but don't expect much support.

Kyle Hughes

Sort State University is available under the MIT license.

See LICENSE for details.