This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Solution Notebook¶

## Constraints¶

• Is a naive solution sufficient?
• Yes
• Are duplicates allowed?
• Yes
• Can we assume the input is valid?
• No
• Can we assume this fits memory?
• Yes

## Test Cases¶

• None -> Exception
• Empty input -> []
• One element -> [element]
• Two or more elements
• Left and right subarrays of different lengths

## Algorithm¶

Wikipedia's animation:

• Recursively split array into left and right halves
• Merge split arrays
• Using two pointers, one for each half starting at index 0
• Add the smaller element to the result array
• Increment pointer where smaller element exists
• Copy remaining elements to the result array
• Return result array

Complexity:

• Time: O(n log(n))
• Space: O(n)

Misc:

• Not in-place
• Most implementations are stable

Merge sort can be a good choice for data sets that are too large to fit in memory, as large chunks of data can be read and written to disk.

Unlike many other sorting algorithms, merge sort is not done in-place.

## Code¶

In [1]:
from __future__ import division

class MergeSort(object):

def sort(self, data):
if data is None:
raise TypeError('data cannot be None')
return self._sort(data)

def _sort(self, data):
if len(data) < 2:
return data
mid = len(data) // 2
left = data[:mid]
right = data[mid:]
left = self._sort(left)
right = self._sort(right)
return self._merge(left, right)

def _merge(self, left, right):
l = 0
r = 0
result = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
# Copy remaining elements
while l < len(left):
result.append(left[l])
l += 1
while r < len(right):
result.append(right[r])
r += 1
return result


## Unit Test¶

In [2]:
%%writefile test_merge_sort.py
import unittest

class TestMergeSort(unittest.TestCase):

def test_merge_sort(self):
merge_sort = MergeSort()

print('None input')
self.assertRaises(TypeError, merge_sort.sort, None)

print('Empty input')
self.assertEqual(merge_sort.sort([]), [])

print('One element')
self.assertEqual(merge_sort.sort([5]), [5])

print('Two or more elements')
data = [5, 1, 7, 2, 6, -3, 5, 7, -1]
self.assertEqual(merge_sort.sort(data), sorted(data))

print('Success: test_merge_sort')

def main():
test = TestMergeSort()
test.test_merge_sort()

if __name__ == '__main__':
main()

Overwriting test_merge_sort.py

In [3]:
%run -i test_merge_sort.py

None input
Empty input
One element
Two or more elements
Success: test_merge_sort
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://nbviewer.jupyter.org/github/donnemartin/interactive-coding-challenges/blob/master/sorting_searching/merge_sort/merge_sort_solution.ipynb", "fetch_time": 1606935486000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2020-50/segments/1606141715252.96/warc/CC-MAIN-20201202175113-20201202205113-00437.warc.gz", "warc_record_offset": 410643496, "warc_record_length": 6356, "token_count": 668, "char_count": 2558, "score": 3.6875, "int_score": 4, "crawl": "CC-MAIN-2020-50", "snapshot_type": "latest", "language": "en", "language_score": 0.6304398775100708, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00016-of-00064.parquet"}