Instruction
Code for Merge Sort
Python
# You may recognize this code at the top by now; it just loads a file
# full of numbers into a list.
import sys
from load import load_numbers
numbers = load_numbers(sys.argv[1])
# 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
# Finally, we need to kick the whole process off. We'll call the
# merge_sort function with the list of numbers we loaded, and print
# the result.
print(merge_sort(numbers))
Save the above code to a file named merge_sort.py
, in the same directory as load.py
. To use it on our file with eight numbers, run:
python merge_sort.py numbers/8.txt
JavaScript
const test_values = [29, 100, 1, 2, 57, 28, 88, 3, 50, 67, 37, 1, 32, 20];
function merge_sort(values) {
if (values.length <= 1) {
return values;
}
const middle_index = Math.floor(values.length / 2);
const left_values = merge_sort(values.slice(0,middle_index));
const right_values = merge_sort(values.slice(middle_index));
let sorted_values = [];
let left_index = 0;
let right_index = 0;
while (left_index < left_values.length && right_index < right_values.length) {
if (left_values[left_index] < right_values[right_index]) {
sorted_values.push(left_values[left_index]);
left_index += 1;
} else {
sorted_values.push(right_values[right_index]);
right_index += 1;
}
}
sorted_values = sorted_values.concat(left_values.slice(left_index));
sorted_values = sorted_values.concat(right_values.slice(right_index));
return sorted_values;
}
const sorted = merge_sort(test_values);
console.log(sorted);
Java
import java.util.*;
public class Sort {
static List<Integer> mergeSort(List<Integer> list) {
if (list.size() <= 1) {
return list;
}
int middleIndex = list.size() / 2;
List<Integer> leftList =
mergeSort(list.subList(0, middleIndex));
List<Integer> rightList =
mergeSort(list.subList(middleIndex, list.size()));
List<Integer> sortedList = new ArrayList<Integer>();
int leftIndex = 0;
int rightIndex = 0;
int leftLength = leftList.size();
int rightLength = rightList.size();
while (leftIndex < leftLength && rightIndex < rightLength) {
if (leftList.get(leftIndex) < rightList.get(rightIndex)) {
sortedList.add(leftList.get(leftIndex));
leftIndex++;
} else {
sortedList.add(rightList.get(rightIndex));
rightIndex++;
}
}
sortedList.addAll(leftList.subList(leftIndex, leftLength));
sortedList.addAll(rightList.subList(rightIndex, rightLength));
return sortedList;
}
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(32, 100, 1, 2, 29, 28, 88, 3, 50, 67, 37, 1, 57, 20));
System.out.println(mergeSort(list));
}
}