a01_2_merge_sort_algorithm.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Combinatorial Optimization - B.Korte, J.Vygen
Algorithm 1.2
Merge-Sort Algorithm
"""


def merge_sort(a):
    """
    Recursive Merge-Sort

    Returns mapping function {0 .. n-1} -> {0 .. n-1}
    """
    n = len(a)

    # step 1 (stopping condition)
    if n == 1:
        return lambda x: x  # Returns identity mapping.

    # step 2 (call recursive function)
    m = n / 2

    r = merge_sort(a[:m])
    s = merge_sort(a[m:])

    # step 3 (merge two lists)
    ret = [None] * n
    k = 0
    l = 0

    while k < m and l < n - m:
        if a[r(k)] <= a[m + s(l)]:
            ret[k + l] = r(k)
            k += 1
        else:
            ret[k + l] = m + s(l)
            l += 1
    while k < m:
        ret[k + l] = r(k)
        k += 1
    while l < n - m:
        ret[k + l] = m + s(l)
        l += 1
    return lambda x: ret[x]


def merge_sort_simple(a):
    """Returns sorted list."""
    n = len(a)

    if n == 1:
        return a

    r, s = (merge_sort_simple(xs) for xs in (a[:n / 2], a[n / 2:]))
    ret = []
    while r and s:
        ret.append(r.pop(0) if r[0] <= s[0] else s.pop(0))
    return ret + r + s


if __name__ == '__main__':
    for a in ([1, 3, 5, 2, 4, 90, -1, 0, -2],
              ['ac', 'c', 'bc', 'ca', 'bb', 'b'],
              [9.9, 8.8, 7.7, 6.6, 5.5, 4.4, 3.3, 2.2, 1.1, 0.0]):
        f = merge_sort(a)
        print([a[f(i)] for i in range(len(a))])
        print(merge_sort_simple(a))
        print(sorted(a))  # builtin function