Mergesort betrachtet die zu sortierenden Daten als Liste und halbiert und zerlegt sie bis jedes einzelne Element eine Liste ergibt. Bei diesen einzelnen Listen wird dann jede Liste für sich sortiert. Nun beginnt der Algorithmus die Elemente zu verbinden («mergen») und dabei zu sortieren. Dieser Prozess wird wiederholt bis die Gesamtliste wieder zusammengesetzt und sortiert ist.

Zuerst wird die Gesamtliste in kleinere Listen zerlegt («divide») bis jedes einzelne Element eine Liste darstellt.

Danach werden die einzelnen Listen zusammengefügt («to merge») und sortiert. Es entstehen immer grössere sortierte Liste und dies wird wiederholt bis eine sortierte Gesamtliste als Output zurückbleibt.

def merge_sort(meineliste):
	if len(meineliste) > 1:
		mid = len(meineliste) // 2
		left = meineliste[:mid]
		right = meineliste[mid:]

		merge_sort(left)
		merge_sort(right)

		i = 0
		j = 0
		
		k = 0
		
		while i < len(left) and j < len(right):
			if left[i] <= right[j]:
			  
			  meineliste[k] = left[i]
			  i += 1
			else:
				meineliste[k] = right[j]
				j += 1
			k += 1
		
		while i < len(left):
			meineliste[k] = left[i]
			i += 1
			k += 1

		while j < len(right):
			meineliste[k]=right[j]
			j += 1
			k += 1

meineliste = [54,26,93,17,103,3,77,31,44,55,20,6,1,65,253,234]
merge_sort(meineliste)
print(meineliste)