A merge sort works recursively:
- Split the list into two roughly equal halves. Sort each half using mergesort.
- Merge the two halves together.
The pure merge sort will keep dividing until we’re down to a list of one element. Then the merge is trivial (and where the sorting really begins).
Merging is done by maintaining two pointers - one in each list. Compare the values at the two pointers, and then start from the lower value. Add it to the final list. Keep incrementing that pointer until its value is greater than the other pointer, and start incrementing that.
A good check is to see if one of the two sublists is already smaller than the other - then no merging is needed.
Complexity
The complexity is \(\Theta(N\lg N)\) for compares and accesses. It does require extra memory equal to the size of the list.
Variants
- Merge sort can be expensive for small lists, so when the list is below a certain size, switch to a different sort (e.g. insertion sort). Sedgewick recommends switching to insertion sort when the list is 7 elements or less.
- Bottom-Up Mergesort. Instead of being recursive, start from sublists of size 1. Merge together to form sublists of size 2, and so on.
Properties
- Merge sort can be stable if the underlying algorithm is stable, and if the merge is done in a stable fashion.
- The usual merge sort algorithms need double the memory of the list being sorted.
- It can be used for online sorting, where you get a piece of the list at a time. Sort each piece as you get it, and simply apply merge.
Implementations
Python
import heapq
from insertionsort import insertion_sort
from itertools import count, takewhile
def simple_compare(left, right):
"""
Keyword Arguments:
left --
right --
"""
if left < right:
return -1
elif left > right:
return 1
else:
return 0
def heapmerge(lsta, lstb, comparator):
"""
Merge two lists together using the merge in heapq. This currently
only works for numbers - the comparator is ignored.
Keyword Arguments:
lsta -- Left list
lstb -- Right list
comparator -- Comparator function. It should take in two arguments, and
return -1 if the left is smaller, 1 if the right is smaller,
and 0 if they are equal. If none is provided, then it will
assume a numerical sort.
"""
return list(heapq.merge(lsta, lstb))
def simplemerge(lsta, lstb, comparator):
"""
Merge two lists together and return the merged list. This may be
inefficient as I take a lot of slices and produce temporary lists in
several places.
Keyword Arguments:
lsta -- Left list
lstb -- Right list
comparator -- Comparator function. It should take in two arguments, and
return -1 if the left is smaller, 1 if the right is smaller,
and 0 if they are equal. If none is provided, then it will
assume a numerical sort.
"""
new_list = []
index_a = 0
index_b = 0
completed = False
while not completed:
if comparator(lsta[index_a], lstb[index_b]) > 0:
start = index_b
while comparator(lsta[index_a], lstb[index_b]) > 0:
index_b += 1
if index_b == len(lstb):
completed = True
break
new_list.extend(lstb[start:index_b])
if completed:
new_list.extend(lsta[index_a:])
else:
start = index_a
while comparator(lstb[index_b], lsta[index_a]) > 0:
index_a += 1
if index_a == len(lsta):
completed = True
break
new_list.extend(lsta[start:index_a])
if completed:
new_list.extend(lstb[index_b:])
return new_list
def mergesort(lst, merge_method=simplemerge, comparator=simple_compare):
"""
Merge sort. It takes in a list of objects and sorts them based
on the comparator. It only works with a list.
Keyword Arguments:
lst -- List to sort
merge_method -- Function for merging.
comparator -- Comparator function. It should take in two arguments, and
return -1 if the left is smaller, 1 if the right is smaller,
and 0 if they are equal. If none is provided, then it will
assume a numerical sort.
"""
if len(lst) == 1:
return lst
split = len(lst)/2
left = mergesort(lst[:split], merge_method=merge_method,
comparator=comparator)
right = mergesort(lst[split:], merge_method=merge_method,
comparator=comparator)
return merge_method(left, right, comparator=comparator)
def mergesort_insertion(lst, merge_method=simplemerge, comparator=simple_compare,
threshold=8):
"""
Merge sort. Just like the regular merge sort but uses an insertion
sort when the list becomes smaller than the threshold value.
Keyword Arguments:
lst -- List to sort
merge_method -- Function for merging.
threshold -- If the list is smaller than this, it uses an insertion sort.
comparator -- Comparator function. It should take in two arguments, and
return -1 if the left is smaller, 1 if the right is smaller,
and 0 if they are equal. If none is provided, then it will
assume a numerical sort.
"""
if len(lst) < threshold:
insertion_sort(lst)
return lst
split = len(lst)/2
left = mergesort_insertion(lst[:split], merge_method=merge_method,
comparator=comparator, threshold=threshold)
right = mergesort_insertion(lst[split:], merge_method=merge_method,
comparator=comparator, threshold=threshold)
return merge_method(left, right, comparator)
def get_indices(lst_size, step_size):
"""
For the bottom up merge, I need to know the indices from where to
start merging. This is a helper function that provides that.
Keyword Arguments:
lst_size -- Size of list.
step_size -- Step size
"""
return list(takewhile(lambda x: x < lst_size, count(0, step_size)))
def bottomupmerge(lst, merge_method=simplemerge, comparator=simple_compare):
"""
Merge sort done bottom up. This sorts in place!
Keyword Arguments:
lst --
merge_method -- (default simplemerge)
comparator -- (default simple_compare)
"""
sublist_size = 1
while sublist_size < len(lst):
sublist_indices = get_indices(len(lst), 2*sublist_size)
for index in sublist_indices:
try:
pass
lst[index:index+2*sublist_size] = merge_method(
lst[index:index+sublist_size],
lst[index+sublist_size:index+2*sublist_size],
comparator)
except IndexError:
pass
sublist_size *= 2
C++
#include <algorithm>
#include <vector>
#include "insertionsort.cpp"
std::vector<int> mergesort(std::vector<int>& lst);
// When below the threshold, use insertion sort.
std::vector<int> mergesort_insertion(std::vector<int>& lst, int threshold);
std::vector<int> mergesort(std::vector<int>& lst)
{
if (lst.size() == 1)
{
return lst;
}
int split = lst.size() / 2;
std::vector<int> left(lst.begin(), lst.begin()+split);
left = mergesort(left);
std::vector<int> right(lst.begin()+split, lst.end());
right = mergesort(right);
std::merge(left.begin(), left.end(), right.begin(), right.end(),
lst.begin());
return lst;
}
std::vector<int> mergesort_insertion(std::vector<int>& lst, int threshold=8)
{
if (lst.size() < threshold)
{
insertion_sort(lst.begin(), lst.end());
return lst;
}
int split = lst.size() / 2;
std::vector<int> left(lst.begin(), lst.begin()+split);
left = mergesort_insertion(left, threshold);
std::vector<int> right(lst.begin()+split, lst.end());
right = mergesort_insertion(right, threshold);
std::merge(left.begin(), left.end(), right.begin(), right.end(),
lst.begin());
return lst;
}
void bottomup_merge(std::vector<int>& lst)
{
int sublist_size = 1;
while (sublist_size < lst.size())
{
for (std::vector<int>::size_type index=0;
index + sublist_size < lst.size(); index += 2*sublist_size)
{
if (index + 2*sublist_size >= lst.size())
{
std::inplace_merge(lst.begin() + index, lst.begin() + index + sublist_size,
lst.end());
}
else
{
std::inplace_merge(lst.begin() + index, lst.begin() + index + sublist_size,
lst.begin() + index + 2*sublist_size);
}
}
sublist_size *= 2;
}
}