This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Solution Notebook

Problem: Implement merge sort.

Constraints
Test Cases
Algorithm
Code
Unit Test

Constraints

Is a naiive solution sufficient?
- Yes

Test Cases

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
  - Inrement pointer where smaller element exists
- Copy remaining elements to the result array
- Return result array

Complexity:

Time: O(n log(n))
Space: O(n), stable

Code



In [1]:

    
from __future__ import division


def merge(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


def merge_sort(data):
    if len(data) < 2:
        return data
    mid = len(data) // 2
    left = data[0:mid]
    right = data[mid:len(data)]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

Unit Test



In [2]:

    
%%writefile test_merge_sort.py
from nose.tools import assert_equal


class TestMergeSort(object):
    def test_merge_sort(self):
        print('Empty input')
        data = []
        sorted_data = merge_sort(data)
        assert_equal(sorted_data, [])

        print('One element')
        data = [5]
        sorted_data = merge_sort(data)
        assert_equal(sorted_data, [5])

        print('Two or more elements')
        data = [5, 1, 7, 2, 6, -3, 5, 7, -1]
        sorted_data = merge_sort(data)
        assert_equal(sorted_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









    



Empty input
One element
Two or more elements
Success: test_merge_sort