<jupyter_start><jupyter_text>This notebook was prepared by [<NAME>](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).  Challenge Notebook  Problem: Implement merge sort.* [Constraints](Constraints)* [Test Cases](Test-Cases)* [Algorithm](Algorithm)* [Code](Code)* [Unit Test](Unit-Test)* [Solution Notebook](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  AlgorithmRefer to the [Solution Notebook](http://nbviewer.ipython.org/github/donnemartin/interactive-coding-challenges/blob/master/sorting_searching/merge_sort/merge_sort_solution.ipynb).  If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.  Code<jupyter_code>import copy
class MergeSort(object):

    def sort(self, data):
        # TODO: Implement me
        # pass
        length = len(data)
        
        if data is None:
            return None
        
        elif length <= 1:
            return data
        
        else:
            pass
            
    def sort_fastest(self, datas):
        # TODO: Implement me
        # pass
        length = len(datas)
        data = copy.deepcopy(datas)
        
        if data is None:
            return None
        
        elif length <= 1:
            return data
        
        else:
            start = []
            end = []
            while len(data) > 1:

                a = min(data)
                b = max(data)
                
                start.append(a)
                end.append(b)
                
                data.remove(a)
                data.remove(b)
                
            if data: start.append(data[0])
            end.reverse()
 
            return (start + end)<jupyter_output><empty_output><jupyter_text>Unit Test**The following unit test is expected to fail until you solve the challenge.**<jupyter_code># %load test_merge_sort.py
from nose.tools import assert_equal, assert_raises


class TestMergeSort(object):

    def test_merge_sort(self):
        merge_sort = MergeSort()

        print('None input')
        assert_raises(TypeError, merge_sort.sort, None)

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

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

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

        print('Success: test_merge_sort')


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


if __name__ == '__main__':
    main()<jupyter_output>None input
Empty input
One element
Two or more elements
9
7
5
3
[-3, -1, 1, 2, 5, 5, 6, 7, 7]
Success: test_merge_sort
{'fraction_non_alphanumeric': 0.10484668644906034, 'fraction_numerical': 0.009231783712495879, 'mean_word_length': 2.231096911608094, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 13, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '422208', 'license': 'Apache-2.0', 'n_tokens_mistral': 930, 'n_tokens_neox': 869, 'n_words': 257, 'path': 'sorting_searching/merge_sort/merge_sort_challenge.ipynb', 'repo_name': 'lvwuyunlifan/interactive-coding-challenges', 'size': '3039'}