Bottom-up Merge Sort in Erlang and Python

merge_sort.erl

-module(merge_sort).
-export([merge_sort/1]).

% bottom-up merge sort
merge_sort([]) ->
    [];
merge_sort(L) ->
    iterate([[X] || X <- L]).

iterate([Xs]) ->
    Xs;
iterate(Lists) ->
    iterate(merge_lists(Lists)).

merge_lists([Xs, Ys | Rest]) ->
    [merge2(Xs, Ys) | merge_lists(Rest)];
merge_lists(Lists) ->
    Lists.

merge2(Xs=[X | _], [Y | Ys]) when X > Y ->
    [Y | merge2(Xs, Ys)];
merge2([X | Xs], Ys) ->
    [X | merge2(Xs, Ys)];
merge2([], Ys) ->
    Ys.

merge_sort.py

def merge_sort(lst):
    if not lst:
        return []
    lists = [[x] for x in lst]
    while len(lists) > 1:
        lists = merge_lists(lists)
    return lists[0]

def merge_lists(lists):
    result = []
    for i in range(0, len(lists) // 2):
        result.append(merge2(lists[i*2], lists[i*2 + 1]))
    if len(lists) % 2:
        result.append(lists[-1])
    return result

def merge2(xs, ys):
    i = 0
    j = 0
    result = []
    while i < len(xs) and j < len(ys):
        x = xs[i]
        y = ys[j]
        if x > y:
            result.append(y)
            j += 1
        else:
            result.append(x)
            i += 1
    result.extend(xs[i:])
    result.extend(ys[j:])
    return result