Pythonでマージソートを実装してみた

概要

Pythonでマージソートを実装してみました。以下のページを参考にしました。
http://www1.cts.ne.jp/~clab/hsample/Sort/Sort6.html

ソースコード

上記のC言語のfor文をwhileに書き換えましたが、アルゴリズムは新規ではありません。

merge_sort.py

import random

data = {}
data2 = {}
temp = {}
NUM = 10
i = 0
while i < NUM:
    data[i] = random.random()
    i = i + 1

#show
def show_data():
    print("==>> show data")
    i = 0
    while i < NUM:
        print ( str(i) + ":" + str(data[i]) )
        i = i + 1

def show_data2():
    print("==>> show data2")
    i = 0
    while i < NUM:
        print ( str(i) + ":" + str(data2[i]) )
        i = i + 1

#copy
def copy_data_to_data2():
    print("==>> copy data to data2")
    i = 0
    while i < NUM:
        data2[i] = data[i]
        i = i + 1

#merge_sort
def merge_sort(array, left, right):
    print("==>> merge sort")
    mid = 0
    i = 0
    j = 0
    k = 0
    if left >= right:
        return

    mid = int((left + right) / 2)
    merge_sort(array, left, mid)
    merge_sort(array, mid + 1, right)

    i = left
    while i <= mid:
        temp[i] = array[i]
        i = i + 1

    i = mid + 1
    j = right
    while i <= right:
        temp[i] = array[j]
        i = i + 1
        j = j - 1

    i = left
    j = right

    k = left
    while k <= right:
        if temp[i] <= temp[j]:
            array[k] = temp[i]
            i = i + 1
        else:
            array[k] = temp[j]
            j = j - 1
        k = k + 1
            
copy_data_to_data2()
show_data2()
merge_sort(data2, 0, NUM-1)
show_data2()

実行結果

実行できました。アルゴリズムは正常に動いているようです。

$ python3 merge_sort.py 
==>> copy data to data2
==>> show data2
0:0.29081339539145956
1:0.5427579427841487
2:0.7331297206563734
3:0.3809205017667163
4:0.9338518052340457
5:0.6284414307985343
6:0.7340759201674373
7:0.9766655155239733
8:0.4522226565719808
9:0.8563382594665773
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> merge sort
==>> show data2
0:0.29081339539145956
1:0.3809205017667163
2:0.4522226565719808
3:0.5427579427841487
4:0.6284414307985343
5:0.7331297206563734
6:0.7340759201674373
7:0.8563382594665773
8:0.9338518052340457
9:0.9766655155239733

何かの役に立てばと。