MergeSort

struct MergeSort : SortMethod

Block sort, or block merge sort, is a sorting algorithm combining at least two merge operations with an insertion sort to arrive at O(n log n) in-place stable sorting. It gets its name from the observation that merging two sorted lists, A and B, is equivalent to breaking A into evenly sized blocks, inserting each A block into B under special rules, and merging AB pairs.

WikiSort by Mike McFadden is an implementation of “block merge sort”, which is a stable merge sort based on the work described in “Ratio based stable in-place merging”, by Pok-Son Kim and Arne Kutzner. It’s generally as fast as a standard merge sort while using O(1) memory, and can be modified to use additional memory optionally provided to it which can further improve its speed.

The implementation here is a Swift port of Java implementation by Mike McFadden in https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.java

For details and commented code, see the original Java version.

Note that the Java version has a Range class, here we are using the Swift Range<Int> instead.

  • Initializes the Heapsort with the size of the array to sort.

    Declaration

    Swift

    init(arraySize: Int)

  • The array size.

    Declaration

    Swift

    let size: Int

  • Name of the sorting method.

    Declaration

    Swift

    var name: String { get }

  • Description of the sorting method.

    Declaration

    Swift

    var description: String { get }

  • Weblinks to read more information.

    Declaration

    Swift

    var webLinks: [(String, String)] { get }

  • Restarts the sorting method by giving intial values to member variables.

    Declaration

    Swift

    mutating func restart()

  • Executes a step of the sorting.

    Declaration

    Swift

    mutating func nextStep(array: [Int], swappedItems: inout SwappedItems) -> Bool

Helper types

  • Helper data type For details, see the original Java version linked in the comments/docs.

    Declaration

    Swift

    struct Pull

  • Helper data type For details, see the original Java version linked in the comments/docs.

    Declaration

    Swift

    struct Iterator

  • The real algorithm without step-by-step execution.

    Declaration

    Swift

    mutating func realAlgorithm(array: inout [Int])