Instruction
Merge Sort Implementations
Python
# Let's define a recursive merge sort function. As usual, it takes the
# list or sub-list that we want it to sort.
def merge_sort(values):
# Our base case is the same as with Quicksort. If the list has zero or one
# values, there's nothing to sort, so we return it as-is.
if len(values) <= 1:
return values
# If we didn't return, it means we're in the recursive case. So first we need
# to split the list in half. We need to know the index we should split on,
# so we get the length of the list and divide it by 2. So for example if
# there are 8 items in the list, we'll want an index of 4. But what if there
# were an odd number of items in the list, like 7? We can't have an index of
# 3.5, so we'll need to round down in that case. Since we're working in
# Python currently, we can take advantage of a special Python operator that
# divides and rounds the result down: the floor division operator. It
# consists of a double slash.
middle_index = len(values) // 2
# Now we'll use the Python slice syntax to get the left half of the list.
# We'll pass that list to a recursive call to the merge_sort function.
left_values = merge_sort(values[:middle_index])
# We'll also use slice syntax to get the right half of the list, and pass
# that to merge_sort as well.
right_values = merge_sort(values[middle_index:])
# Now we need to merge the two halves together, and sort them as we do it.
# We'll create a list to hold the sorted values.
sorted_values = []
# Now we get to the complicated part - merging the two halves together and
# sorting them as we do it.
# We'll be moving from left to right through the left half of the list,
# copying values over to the sorted_values list as we go. This left_index
# variable will help us keep track of our position.
left_index = 0
# At the same time, we'll also be moving from left to right through the right
# half of the list and copying values over, so we need a separate
# right_index variable to track that position as well.
right_index = 0
# We'll keep looping until we've processed all of the values in both halves
# of the list.
while left_index < len(left_values) and right_index < len(right_values):
# We're looking to copy over the lowest values first. So first we test
# whether the current value on the left side is less than the value on the
# right side.
if left_values[left_index] < right_values[right_index]:
# If the left side value is less, that's what we'll copy to the sorted
# list.
sorted_values.append(left_values[left_index])
# And then we'll move to the next value in the left half of the list.
left_index += 1
# Otherwise, the current value from the right half must have been lower.
else:
# So we'll copy that value to the sorted list instead.
sorted_values.append(right_values[right_index])
# And then we'll move to the next value in the right half of the list.
right_index += 1
# At this point one of the two unsorted halves still has a value remaining,
# and the other is empty. We won't waste time checking which is which.
# We'll just copy the remainder of both lists over to the sorted list.
# The one with a value left will add that value, and the empty one will add
# nothing.
sorted_values += left_values[left_index:]
sorted_values += right_values[right_index:]
# All the numbers from both halves should now be copied to the sorted list,
# so we can return it.
return sorted_values
Swift
Download as an Xcode Playground
import Foundation
/*
We're going to define `mergesort` as a global function that accepts an array. We could define this on an extension of a higher type like `RandomAccessCollection` but that makes the algorithm harder to understand.
Array's `Element` type is defined as a generic type parameter `T` that conforms to `Comparable`
*/
func mergesort<T: Comparable>(_ array: [T]) -> [T] {
// If the list has zero or one values, there's nothing to sort, so we return it as-is
if array.count <= 1 { return array }
// At this point the algorithm is in the recursive portion
// Determine midpoint of array
let mid = array.count/2
// Create left slice of the array and pass through the mergesort function
let left = mergesort(Array(array[0..<mid]))
// Create right half slice and pass through the mergesort function
let right = mergesort(Array(array[mid..<array.count]))
// Merge the two halves together, and sort them in the process
// Create a new array to hold the sorted values
var sorted = Array<T>()
// To eliminate memory reallocation as `sorted` grows, reserve capacity at the
// outset to a number of elements equaling the sum of elements in left and right
sorted.reserveCapacity(left.count + right.count)
// Move from left to right through the left half of the array,
// copying values over to `sorted` in the process. This leftIndex
// variable keeps track of the position in the array
var leftIndex = 0
// Move from left to right through the right half of the array and
// copy values over. Use a separate
// rightIndex variable to track that position as well
var rightIndex = 0
// Keep looping until all of the values in both subarrays
// are processed.
while leftIndex < left.count && rightIndex < right.count {
// Copy the lesser value in to sorted.
// Test whether the current value on the left side is less than the value on the
// right side.
if left[leftIndex] < right[rightIndex] {
// If the left side value is less, copy to `sorted`
sorted.append(left[leftIndex])
// Increment leftIndex to move to next value in left slice
leftIndex += 1
} else {
// Otherwise, copy the current value in right slice to `sorted`
sorted.append(right[rightIndex])
// Increment `rightIndex` to move to next value in right slice
rightIndex += 1
}
}
// At this point one of the two unsorted halves still has a value remaining,
// and the other is empty. We won't waste time checking which is which.
// We'll just copy the remainder of both lists over to the sorted list.
// The one with a value left will add that value, and the empty one will add
// nothing.
sorted.append(contentsOf: left[leftIndex..<left.count])
sorted.append(contentsOf: right[rightIndex..<right.count])
return sorted
}