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:
nlists of one item each.
Write your solution in any language you like. We have solutions below for the following languages:
# 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