 # Mark Miyashita

## 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:

1. Divide the input list into two sublists until you have `n` lists of one item each.
2. 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

``````# 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 < right:
return [left] + merge(left[1:], right)
return [right] + merge(left, right[1:])
``````

``````# !/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
``````