#!/usr/bin/env python
# -*- coding: utf-8 -*-


def merge(arr1, arr2):
    idx = ldx = 0
    l1 = len(arr1)
    l2 = len(arr2)
    tmp = []
    while idx < l1 and ldx < l2:
        a, b = arr1[idx], arr2[ldx]
        if a < b:
            tmp.append(a)
            idx += 1
        else:
            tmp.append(b)
            ldx += 1

    return tmp + arr1[idx:] + arr2[ldx:]


def sort(arr):
    l = len(arr)
    if l < 2:
        return arr
    elif l == 2:
        a, b = arr
        return [a, b] if a < b else [b, a]
    else:
        mdx = len(arr) / 2
        arr1, arr2 = arr[:mdx], arr[mdx:]
        return merge(sort(arr1), sort(arr2))


if __name__ == "__main__":
    import unittest

    class Tests(unittest.TestCase):

        def test_sort_0(self):
            self.assertEqual([], sort([]))

        def test_sort_1(self):
            self.assertEqual([1], sort([1]))

        def test_sort_2(self):
            self.assertEqual([1, 2], sort([2, 1]))

        def test_sort_3(self):
            self.assertEqual(
                [1, 2, 3, 4, 5],
                sort([2, 3, 4, 5, 1])
            )

        def test_sort_4(self):
            self.assertEqual(
                list(range(100)),
                sort(list(reversed(range(100))))
            )

    unittest.main()