合併排序法

導航：首頁 > 程式語言、邏輯學> 合併排序法

merge_sort.py

#!/usr/bin/env python
#合併排序法 marge sort
import math

def merge_sort_aux(array, p, q):
    mean = math.floor((p+q)/2)
    if q - p <= 1:
        return array
    else:
        print(p, q, mean,array[p:q])
        array = merge_sort_aux(array, p, mean)
        array = merge_sort_aux(array, mean,q)
        array = merge(array, p, mean, q)    
        return array

def merge(array, l, m, r):
    array_l = array[l:m]
    array_r = array[m:r]

    i = 0
    j = 0
    k = l

    array_l_length = m - l

    array_r_length = r - m

    while i < array_l_length and j < array_r_length:
        if array_l[i] <= array_r[j]:
            array[k] = array_l[i]
            i += 1
        else:
            array[k] = array_r[j]
            j += 1
        k += 1
    
    if i == array_l_length:
        while j < array_r_length:
            array[k] = array_r[j]
            j += 1
            k += 1
    if j == array_r_length:
        while i < array_l_length:
            array[k] = array_l[i]
            i += 1 
            k += 1
    
    return array


def merge_sort(array):
    return merge_sort_aux(array, 0, len(array))

array = [3,1,4,1,5,9,2,6]
print(merge_sort(array))