Merge Sort

Merge sort is a popular conquer and divide sorting algorithm. If you haven’t heard of it before, you should check out the Wikipedia page here. It has a nice visualization of the algorithm in action.

A basic outline of the algorithm is as follows:

Divide the input list into two sublists until you have n lists of one item each.
Repeatedly merge the two sublists together until you obtain the sorted list.

Write your solution in any language you like. We have solutions below for the following languages:

Python

Ruby

Python Solution (download)

# Merge Sort Python Solution
# By: Mark Miyashita

def merge_sort(lst):
    """Sorts the input list using the merge sort algorithm.

    >>> lst = [4, 5, 1, 6, 3]
    >>> merge_sort(lst)
    [1, 3, 4, 5, 6]
    """
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)

def merge(left, right):
    """Takes two sorted lists and returns a single sorted list by comparing the
    elements one at a time.

    >>> left = [1, 5, 6]
    >>> right = [2, 3, 4]
    >>> merge(left, right)
    [1, 2, 3, 4, 5, 6]
    """
    if not left:
        return right
    if not right:
        return left
    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])

Ruby Solution (download)

# !/usr/bin/env ruby
# Merge Sort Ruby Solution
# By: Mark Miyashita

def merge_sort(lst)
  if lst.length <= 1
    lst
  else
    mid = (lst.length / 2).floor
    left = merge_sort(lst[0..mid - 1])
    right = merge_sort(lst[mid..lst.length])
    merge(left, right)
  end
end

def merge(left, right)
  if left.empty?
    right
  elsif right.empty?
    left
  elsif left.first < right.first
    [left.first] + merge(left[1..left.length], right)
  else
    [right.first] + merge(left, right[1..right.length])
  end
end

Mark Miyashita

negativetwelve

Merge Sort

Python Solution (download)

Ruby Solution (download)