MergeSort
public struct MergeSort<Element> : Identifiable
extension MergeSort: SortingAlgorithm
extension MergeSort: Codable where Element: Codable
extension MergeSort: Equatable where Element: Equatable
extension MergeSort: Hashable where Element: Hashable
A divide-and-conquer sorting algorithm.
-
A type that represents the collection of the elements that the algorithm is sorting.
Declaration
Swift
public typealias Elements = Array<Element>
-
The stable identity of the algorithm.
Declaration
Swift
public let id: UUID
-
The given elements that the algorithm is sorting.
This value is constant and will not change after instantiation.
Declaration
Swift
public let input: Elements
-
The position of the first element in the left paritition to be merged.
Whether the algorithm is finished or not cannot be inferred from this value.
Declaration
Swift
public private(set) var currentIndex: Elements.Index { get }
-
The merge that is currently underway.
This value will be
nil
when the algorithm has not started and when the algorithm is finished. Otherwise, a merge will always be ongoing and a value will always be returned.Declaration
Swift
public private(set) var ongoingMerge: Merge? { get }
-
The current result of applying the sorting algorithm to
input
.This value is “live” and will change as the algorithm is executed. When the algorithm is finished this value will contain the sorted result of
input
. It is primarily exposed to allow the internals of the algorithm to be observed.This value should not be used as the final output of the algorithm unless it is known that the algorithm has finished. It may be easier to perform
callAsFunction()
and respond to the step that is returned – the output will be reported through that function if the algorithm is finished.See also
outputAfterTransactions
Declaration
Swift
public private(set) var output: Elements { get }
-
The number of elements in each partition being merged.
The algorithm is finished when this value is greater-than-or-equal-to the number of elements in
input
.Declaration
Swift
public private(set) var partitionSize: Int { get }
-
Creates an algorithm to sort the given input using bottom-up merge sort.
Declaration
Swift
public init(input: Elements)
Parameters
input
The elements to sort.
-
The value of
output
after applying the uncommitted transactions from the ongoing merge.This should not be used for general access to
output
.This is useful for observing the merging process happen to
output
. Due to implementation details, the outcome of a single merge will only be applied after all of the comparisons for that merge have been answered. Thus,output
will only update inpartitionSize * 2
-sized chunks. This value allows a caller to inspectoutput
with all of the in-flight transactions from the merge applied, which will show the merge happen step-by-step to the partitions withinoutput
.If there is no ongoing merge then this value will be equal to
output
.See also
MergeSort.Merge.output
Declaration
Swift
public var outputAfterTransactions: Elements { get }
-
An algorithm that takes an array with two sorted partitions and produces one sorted partition in their place.
This algorithm operates entirely on indices and comparisons so there it has no need to pass arrays or copy elements. The partitions are defined by the bounds created from indices, and the output are transactions that need to be applied to the source array.
The left partition is the elements in the source array between [
fromIndex
,middleIndex
].The right partition is the elements in the source array between (
See moremiddleIndex
,toIndex
).Declaration
Swift
public struct Merge : Codable, Equatable, Hashable, Identifiable
-
The runtime complexity of the algorithm.
Declaration
Swift
public static var complexity: Complexity { get }
-
The unique name of the sorting algorithm.
Declaration
Swift
public static var label: SortingAlgorithmLabel { get }
-
Returns the number of comparisons that the algorithm will perform, in the worst case, given an input with
n
elements.The algorithm may require fewer total comparisons than returned depending on the state of the input and the answers to the comparisons. The algorithm is guaranteed to not require more comparisons than returned.
This value is provably correct and precise. It is not an estimate.
See also
https://oeis.org/A003071Declaration
Swift
public static func calculateMaximumNumberOfComparisonsInWorstCase(for n: Int) -> Int
Parameters
n
The number of elements.
Return Value
The number of comparisons that the algorithm will perform in the worst case.
-
Answers the current comparison with the given side.
The algorithm is advanced to the state that follows the answer.
If the algorithm is not at a point of comparison then this function will have no effect.
Declaration
Swift
public mutating func answer(_ answer: Comparison<`Self`>.Side)
Parameters
answer
The answer to the current comparison.
-
Executes the algorithm in its current state and, if possible, advances it to the next state and returns the step to the caller.
When the algorithm is not finished this function will return the next comparison that needs to be answered to continue the algorithm. When the algorithm is finished this function will return the sorted output.
This function is idempotent: for a given state of the algorithm, calling this function will always produce the same result and will always leave the algorithm in the same – possibly new – state. Performing this function consecutively on the same algorithm will have no additional affect.
Declaration
Swift
public mutating func callAsFunction() -> SortingAlgorithmStep<`Self`>
Return Value
The next step in the algorithm: either the next comparison to answer, or the sorted output.
-
Returns the element that represents the given side of the current comparison.
If the algorithm is not at a point of comparison then
nil
will be returned. For example, if the algorithm has not started or is finished thennil
will be returned.Declaration
Swift
public func peekAtElement(for answer: Comparison<MergeSort<Element>>.Side) -> Element?
Parameters
answer
The answer that represents the side of the comparison to peek at.
Return Value
The element that represents the given side of the current comparison, or
nil
if the algorithm is not at a point of comparison.