Merge

public struct Merge : Codable, Equatable, Hashable, Identifiable

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 (middleIndex, toIndex).

  • The position of the first element in the left paritition.

    Declaration

    Swift

    public let fromIndex: MergeSort.Elements.Index
  • id

    The stable identity of the merge.

    Declaration

    Swift

    public let id: UUID

  • The position of last element in the left partition.

    The next index is the position of the first element in the right partition.

    Declaration

    Swift

    public let middleIndex: MergeSort.Elements.Index

  • The position past the last element in the right partition.

    Declaration

    Swift

    public let toIndex: MergeSort.Elements.Index

  • The current position of the element being compared on behalf of the left partition.

    This is the position of the element represented by Comparison.left when this is the ongoing merge.

    Declaration

    Swift

    public private(set) var leftPartitionIndex: MergeSort.Elements.Index { get }

  • The transactions that need to be applied to the original array to sort the two sub-lists.

    This value is “live” and will grow as the merge is executed. When the merge is finished this value will contain all of the transactions that need to be applied to the original array. It is primarily exposed to allow the internals of the merge to be observed.

    This value should not be used as the final output of the merge 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

    MergeSort.outputAfterTransactions

    Declaration

    Swift

    public private(set) var output: Set<Transaction> { get }

  • The position in the outut of the winner of the comparison between the elements at leftPartitionIndex and rightPartitionIndex.

    Declaration

    Swift

    public private(set) var outputIndex: MergeSort.Elements.Index { get }

  • The current position of the element being compared on behalf of the right partition.

    This is the position of the element represented by Comparison.right when this is the ongoing merge.

    Declaration

    Swift

    public private(set) var rightPartitionIndex: MergeSort.Elements.Index { get }

Public Initialization

  • Creates an algorithm to merge two sorted partitions within the current output of an ongoing merge sort.

    Declaration

    Swift

    public init(
    fromIndex: MergeSort.Elements.Index,
    middleIndex: MergeSort.Elements.Index,
    toIndex: MergeSort.Elements.Index
)

    Parameters

    fromIndex

    The position of the first element in the left paritition.
    middleIndex

    The position of last element in the left partition.
    toIndex

    The position past the last element in the right partition.

Public Instance Interface

  • Returns a Boolean value indicating whether both the leftPartitionIndex and rightPartitionIndex are within the bounds of their respective partitions.

    This value is false if either side is out of bounds.

    Declaration

    Swift

    public var arePartitionIndicesInBounds: Bool { get }

  • Answers the current comparison with the given side.

    The merge is advanced to the state that follows the answer. If the answer is left then the leftTransaction will be added to output, otherwise the rightTransaction will be added to output.

    Declaration

    Swift

    public mutating func answer(_ answer: Comparison<MergeSort>.Side)

    Parameters

    answer

    The answer to the current comparison.

  • Returns the output of the merge if it is finished.

    If the merge is finished then the returned value is equal to output. If the merge is not finished then the returned value is equal to nil.

    Declaration

    Swift

    public mutating func callAsFunction() -> Set<Transaction>?

MergeSort.Merge.Transaction Definition

  • A description of a move to be made in the source array to perform the merge.

    A transaction is focused on a single element in the source array being moved to another position.

    See more

    Declaration

    Swift

    public struct Transaction : Codable, Equatable, Hashable