Mergesort
Einfache Sprache
Mergesort ist ein Sortierverfahren. Dabei wird ein Teile-und-Beherrsche-Ansatz benutzt.
Idee Mergesort
Die zu sortierende Liste wird in zwei Listen aufgeteilt. Diese werden einzeln sortiert. Die sortierten Teillisten werden dann klever zusammengefügt. Dabei Nutzt man den Fakt aus das sie Sortiert sind. Nach dem Prinzip der Rekursion wird das Aufteilen immer wieder wiederholt bis ein Basisfall erreicht ist.
Algorithmus
1def mergesort(S):
2 n = len(S)
3 if n >= 2:
4 m = n // 2
5 S1 = [0] * m
6 S2 = [0] * (n - m)
7
8 for i in range(m):
9 S1[i] = S[i]
10 for i in range(n - m):
11 S2[i] = S[m + i]
12
13 mergesort(S1)
14 mergesort(S2)
15 merge(S1, S2, S)
16
17def merge(A, B, C):
18 a = len(A)
19 b = len(B)
20 i = j = k = 0
21
22 while i < a or j < b:
23 if i == a:
24 for l in range(j, b):
25 C[k] = B[l]
26 k += 1
27 j = b
28 else:
29 if j == b:
30 for l in range(i, a):
31 C[k] = A[l]
32 k += 1
33 i = a
34 else:
35 if A[i] <= B[j]:
36 C[k] = A[i]
37 i += 1
38 else:
39 C[k] = B[j]
40 j += 1
41 k += 1
Laufzeit
Mergesort hat eine Laufzeit von $\mathcal O(n\log n)$.