Merge Sort

سلام. این بار با یک الگوریتم بسیار موثر مرتب سازی به نام Merge Sort آشنا می شیم. پیچیدگی زمانی این الگوریتم (O(nlogn هست. ایده های اولیه تشکیل دهنده این الگوریتم:

۱- Recursive behaviour

۲- ترکیب لیست های مرتب شده

 

---

def merge (a, b):
    ca = len(a)
    cb = len(b)
    lst = []
    while len(lst) < len(a) + len(b):
        if ca != 0 and cb != 0:
            if a[-ca] >= b[-cb]:
                        lst.append(b[-cb])
                        cb -= 1
            else:
                        lst.append(a[-ca])
                        ca -= 1
        else:
            if ca == 0:
                        lst.append(b[-cb])
                        cb -= 1
            else:
                        lst.append(a[-ca])
                        ca -= 1
    return lst

def MergeSort(ar, n):
    pivot = n/2
    if n <= 1:
        return ar
    else:
        return merge(MergeSort(ar[:pivot], pivot), MergeSort(ar[pivot:], n-pivot))

n = input("size of array: ")
ar = [int(x) for x in raw_input("enter array: ").split()]

print " ".join(str(x) for x in MergeSort(ar, n))