Pythonでマージソートを書く

開発環境はWindows7 Professional(32bit) + ActivePython 2.7.10.12(Python 2.7.10)

マージソートとは、ソートの一種で、数列を分割して、それぞれをソートして、最後に、分割されたファイルを比較しながら、1つに統合していくアルゴリズムです。

arr = [5,9,2,4,8,6,1,3,7]
ar1 = arr[0::2]
ar2 = arr[1::2]


# メソッドを作ったが、作らずに、list.sortメソッドで良い。
def st(ar1):

	dummy = None
	while True:

		flug = True

		for i in range(len(ar1)):
			if i < len(ar1)-1 and ar1[i] > ar1[i+1]:
				dummy = ar1[i+1]
				ar1[i+1] = ar1[i]
				ar1[i] = dummy
				flug = False

		if flug == True:
			break

	return ar1

def merge(ar1,ar2):
	ar1 = st(ar1) # ar1.sort()でも良い
	ar2 = st(ar2) # ar2.sort()でも良い
	ar3 = []

	num = len(ar1)

	if len(ar1) >= len(ar2):
		num = len(ar2)

	while True:
		
		if len(ar1) == 0 and len(ar2) == 0:
			break

		elif len(ar1) == 0 or len(ar2) == 0:
			if len(ar1) == 0:
				ar3.append(ar2[0])
				del ar2[0]
			else:
				ar3.append(ar1[0])
				del ar1[0]
		else:

			if ar1[0] < ar2[0]:
				ar3.append(ar1[0])
				del ar1[0]
			else:
				ar3.append(ar2[0])
				del ar2[0]

	return ar3

print(merge(ar1,ar2)) # [1, 2, 3, 4, 5, 6, 7, 8, 9]