Instruction

Alternate Versions of Merge Sort

Swift

In the previous implementation of merge sort, we carry out an array slicing operation when splitting the array in two. There is a cost to this operation that needs to be considered.

Merge sort is traditionally a O(n log n) algorithm. The split step takes logarithmic time overall with an n number of merges in total. Generally, creating an array slice in Swift does not incur a cost. Slices are views into arrays and share the same storage. It is only when a new array is created from a slice that the values are copied to a new location in memory. At this point the values need to be read from the original array and copied into the new one. This incurs a runtime cost of O(k) where k is the size of the slice.

Any merge sort algorithm that uses array slicing as part of the splitting logic incurs this cost. Following is an implementation that avoids list slicing by using variables to keep track of the portions of the array being worked on.

This version of merge sort mutates the array being passed in. Note that this is not an in place merge sort and the space complexity is still O(n).

func mergesort<T: Comparable>(_ array: inout [T], range: ClosedRange<Int>? = nil) {}

We've declared mergesort as a generic function with a type parameter T that conforms to Comparable.

The function accepts an array as the first argument. Note that the argument is marked as inout. This allows the array to be passed by reference so that it can be mutated.

The second argument, range, accepts a range argument to denote the start and end index of the array. The algorithm will only consider values in between the upper and lower bound of the range when splitting and merging.

The arguments have a default value of nil so that calling the function is easier.

let range = range ?? array.startIndex...array.index(before: array.endIndex)

If the initial value of range is nil, let's define the range to start at the startIndex of the array and end at the index before endIndex.

We're defining this range to be of type ClosedRange<Int> instead of CountableRange<Int>. This is because in a closed range, the upperBound property accurately reflects the upper bound defined on the range. On an instance of CountableRange, a range defined as 0..<10, has an upper bound of 10, instead of 9. This makes the midpoint calculation unnecessarily complicated.

Next, we need to determine the midpoint of the array. Typically all we have to do is divide the size of the array in half. Since we have a single array to work with, size is always going to be the same value and will return an incorrect midpoint. Since range.lowerBound refers to the starting index of the list and range.upperBound refers to the index of the last element, we can calculate the size of the array by deducting the lower bound from the upper bound and dividing in half. This alone won't always equal the midpoint index however.

Consider an array [1,2,3,4,5,6]. On the first pass, range.lowerBound is 0 and range.upperBound is 5.

(range.upperBound - range.lowerBound)/2 equals 2 which is the correct midpoint. So far so good. The next step in mergesort is to recursively call mergesort on the array again until we get to single element arrays. Since we're not actually splitting the array we achieve this step by calling the function and passing in different variables for start and end to indicate how the array was "split"

For the left side we'll call:

mergesort(&array, range: range.lowerBound...mid)

We're passing in the same array here (ignore the & symbol for a bit), for range we're passing a range that goes from range.lowerBound all the way up to mid.

On this run of mergesort (on the left half), if we calculate mid we end up with index position 1, which is the value expected.

The issue arises when we try to calculate mid for the right half. Let's go back to when the midpoint was index position 5. To work on the right half of the array, we would call mergesort like this

mergesort(&array, range: indexAfterMid...range.upperBound)

Here we're telling the mergesort algorithm that the values in the "right half" are those that go from the index position after mid all the way to the end. Only the values between those index values are considered.

Using our current formula, let's calculate mid:

mid = (5-2)/2 = 1

But an index position of 1 is not the right midpoint for the half array. If we look at the array [1,2,3,4,5,6], the correct midpoint for values in the right half ([4,5,6]) is at index position 4 in the original list.

We can get the correct value every time if we add range.lowerBound to the current mid. For the "left" side of the array, rage.lowerBound is always 0 so adding start doesn't affect the midpoint calculation. On the right side adding range.lowerBound results in the correct value. In our example above, range.lowerBound is 3. Adding 3 to the value obtained from the midpoint calculation (1) results in a mid value of 4.

let mid = ((range.upperBound - range.lowerBound)/2) + range.lowerBound

We're going to use the index position after mid as well so let's define a constant to hold on to this value instead of just adding 1.

let indexAfterMid = mid + 1

As long as the lower bound of the range is less than the mid point we'll call mergesort on the "left" half. Whem the lower bound of the range equals the midpoint then we're down to considering just one element in the array

If it isn't, we'll call mergesort and pass the array with a range going from the start of the array to the current midpoint

if range.lowerBound < mid {
    mergesort(&array, range: range.lowerBound...mid)
}

As long as the index after the midpoint is less than or equal to the upper bound of the range, we'll evaluate the right half of the array. When index after mid is greater than the upper bound, we're considering just one element in the right half.

We're also checking to see if the distance between the upperBound and lowerBound of the range is 1. If it is, we have a single element array.

If both checks are satisfied, we'll call mergesort, pass in the array and define the range to go from the index after the mid point all the way to the end.

if indexAfterMid <= range.upperBound && (range.upperBound - range.lowerBound) != 1 {
    mergesort(&array, range: indexAfterMid...range.upperBound)
}

As we keep calling mergesort, we keep redefining the range into smaller and smaller values until we're at our base case where the checks fail and we're considering single elements in the array.

At this point we can merge and sort in the process. We'll assign the lower bound to a leftIndex variable and the indexAfterMid to rightIndex. Using these two variables we can walk down the array comparing values

var leftIndex = range.lowerBound
var rightIndex = indexAfterMid

We also need an empty array to hold the sorted values. We can eliminate memory reallocations as the array grows by giving it a size equivalent to the number of elements we're currently evaluating.

var sorted = Array<T>()
let leftDistance = indexAfterMid - leftIndex
let rightDistance = range.upperBound - rightIndex
sorted.reserveCapacity(leftDistance + rightDistance)

Next we're going to keep looping over the array until values in the respective halves have been processed.

while leftIndex < indexAfterMid && rightIndex <= range.upperBound {
    let leftValue = array[leftIndex]
    let rightValue = array[rightIndex]
}

If the left value is left than the right value, we add it to the sorted array and increment leftIndex.

if leftValue < rightValue {
    sorted.append(leftValue)
    leftIndex += 1
} else {
}

Otherwise we append rightValue to the sorted array and increment rightIndex

sorted.append(rightValue)
rightIndex += 1

At the end of the loop some elements from either the left half or right half may not have been processed. Let's loop over the rest and assign them to sorted.

while leftIndex < indexAfterMid {
    sorted.append(array[leftIndex])
    leftIndex += 1
}

while rightIndex <= range.upperBound {
    sorted.append(array[rightIndex])
    rightIndex += 1
}

Once we've read values at certain indices in array, we can replace them with the values from sorted since the values at these indices will not be read again.

var sortedIndex = range.lowerBound

for i in sorted {
    array[sortedIndex] = i
    sortedIndex += 1
}

In this way we mutate the original array and sort it.

var test = [29, 100, 1, 2, 57, 28, 88, 3, 50, 67, 37, 1, 32, 20]
mergesort(&test)

Introduction to Data Structures

Alternate Versions of Merge Sort

Swift