Mergesort

Das Sortieren einer Liste gehört zu den Standardübungen beim Programmieren.

Mergesort wurde zum ersten Mal von John von Neumann präsentiert. Vgl. Art. s.v. Mergesort in Wikipedia. Die Idee ist, dass eine Liste, die aus einem Element besteht, bereits sortiert ist. Um eine größere List zu sortieren, muss man also nur eine Liste teilen können, bis jeder Teil sortiert ist und dann die entstandenen Teile neu sortiert zusammensetzen.

Implementierung in Python am Beispiel von Zeichenketten:

# ein Zeichen in eine sortierte Kette einfuegen
def eins_sortiert_einfuegen(p,q):
    z = 0
    for n in q:
        if p <= n:
            return q[:z]+p+q[z:]
        z = z + 1
    return q+p

# viele unsortierte Zeichen in eine sortierte Kette einfuegen
def viele_sortiert_einfuegen(a, b):
    y = 0
    for n in a:
        b = eins_sortiert_einfuegen(n, b)
    return b

# zwei sortierte Ketten sortiert miteinander verbinden
def merge(a,b):
    x = 0
    for m in a:
        t = 0
        y = len(b)
        for n in range(x, y):
            if m <= b[n]:
                b = b[:n]+m+b[n:]
                x = n
                break
        if y == len(b):
            b = b + m
            x = n + 1
    return b

def mergesort(zeichenkette):
    a = len(zeichenkette)
    if a > 1: 
        #return viele_sortiert_einfuegen(
              mergesort(zeichenkette[:int(a/2)]), 
                     mergesort(zeichenkette[int(a/2):])
                                        )
        return merge(mergesort(zeichenkette[:int(a/2)]),
                       mergesort(zeichenkette[int(a/2):]))
    else: return zeichenkette

## Voruebung
print eins_sortiert_einfuegen("r", "abcmnopz")
print viele_sortiert_einfuegen("rdz", "abcmnopz")

## Sortierung
print mergesort("rio bravo john hugo")