Sorting(7) Merge Sort(합병 정렬)

파이썬 Merge Sort로 오름차순으로 정렬하는 방식입니다.

시간복잡도 : O(nlogn)

(CASE 1)

def mergeSort(A):

    left = []

    right = []

    

    if len(A) > 1:

        mid = len(A) / 2

        for l in range(0, mid, 1):

            left.append(A[l])

        for r in range(mid, len(A), 1):

            right.append(A[r])

        mergeSort(left)

        mergeSort(right)

        

        i=j=k=0

        

        while i < len(left) and j < len(right):

            if left[i] < right[j]:

                A[k]=left[i]

                i += 1

            else:

                A[k]=right[j]

                j += 1

            k += 1

        while i < len(left):

            A[k]=left[i]

            i += 1

            k += 1

        while j < len(right):

            A[k]=right[j]

            j += 1

            k += 1

if __name__ == '__main__':

    A= [1, 8, 6, 10, 4, 5, 3, 22]

    mergeSort(A)

    print A

(CASE 2)

def merge_sort(A, first, last):

    mid = 0

    if first < last:

        mid = (first + last) / 2

        merge_sort(A, first, mid)

        merge_sort(A, mid+1, last)

        merge(A, first, last)

def merge(A, first, last):

    temp = []

    mid = (first + last) / 2

    i = first

    j = mid + 1

    k = 0

    while i <= mid and j <= last:

        if A[i] <= A[j]:

            temp.append(A[i])

            i += 1

        else:

            temp.append(A[j])

            j += 1

    if i > mid:

        for t in range(j, last+1):

            temp.append(A[t])

    else:

        for t in range(i, mid+1):

            temp.append(A[t])

    

    for t in range(first, last+1, 1):

        A[t] = temp[k]

        k += 1

    

if __name__ == '__main__':

    A= [1, 8, 6, 10, 4, 5, 3, 22]

    merge_sort(A, 0, len(A)-1)

    print A