algorithms: merge sort

merge_sort.py

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

from typing import List


def merge_sort(array: List[int]):
    if len(array) <= 1:
        return
    mid = len(array) // 2
    left_side = array[:mid]
    right_side = array[mid:]

    merge_sort(left_side)
    merge_sort(right_side)

    left_idx = right_idx = idx = 0
    while left_idx < len(left_side) and right_idx < len(right_side):
        if left_side[left_idx] > right_side[right_idx]:
            array[idx] = right_side[right_idx]
            right_idx += 1
        else:
            array[idx] = left_side[left_idx]
            left_idx += 1
        idx += 1

    if left_idx < len(left_side):
        while idx < len(array):
            array[idx] = left_side[left_idx]
            left_idx += 1
            idx += 1
    if right_idx < len(right_side):
        while idx < len(array):
            array[idx] = right_side[right_idx]
            right_idx += 1
            idx += 1

merge_sort_test.py

"""Tests for merge_sort.py"""

import pytest

from merge_sort import merge_sort


def test_empty_list():
    unsorted = []
    merge_sort([])
    assert unsorted == []


def test_one_element():
    unsorted = [1]
    merge_sort(unsorted)
    assert unsorted == [1]

    unsorted = [323.23]
    merge_sort(unsorted)
    assert unsorted == [323.23]


@pytest.mark.parametrize(
    "unsorted, sorted",
    [([2, 3, 1], [1, 2, 3]), ([12, 11, 13, 5, 6, 7], [5, 6, 7, 11, 12, 13])],
)
def test_multiple_elements(unsorted, sorted):
    merge_sort(unsorted)
    assert unsorted == sorted


def test_with_negative():
    unsorted = [12, -11, 13, 5000, -5, 6, 7]
    merge_sort(unsorted)
    assert unsorted == [-11, -5, 6, 7, 12, 13, 5000]


def test_with_floats():
    unsorted = [0.0, 76.23, 1.22, 5.5, 5.4]
    merge_sort(unsorted)
    assert unsorted == [0.0, 1.22, 5.4, 5.5, 76.23]


def test_with_negative_floats():
    unsorted = [0.0, 76.23, 1.22, -5.5, 5.4]
    merge_sort(unsorted)
    assert unsorted == [-5.5, 0.0, 1.22, 5.4, 76.23]