Merged Sort

Merge Sort

Merge Sort atau Urut gabung merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk pengurutan data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar dengan prinsip divide and conquer.

Cara kerja algoritme merge sort :

1.    membagi  larik data yang diberikan menjadi dua bagian yang lebih kecil.

2.    Larik yang baru tersebut kemudian akan diurutkan secara terpisah

3.    Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya. 

Contoh penerapan atas sebuah larik sebagai data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2} adalah sebagai berikut:

• Larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}
• Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}
• Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik tersebut {1}, sementara nilai-nilai dalam masing larik {3, 4, 9} dan {2, 5} (nilai 1 dalam elemen larik ke dua telah dipindahkan ke larik baru)
• langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik baru yang dibuat sebelumnya.
• {1, 2} <-> {3, 4, 9} dan {5}
• {1, 2, 3} <-> {4, 9} dan {5}
• {1, 2, 3, 4} <-> {9} dan {5}
• {1, 2, 3, 4, 5} <-> {9} dan {null}
• {1, 2, 3, 4, 5, 9} <-> {null} dan {null}

Kode Program Merge Sort:
# Functiont to sort data in merge sort algorithm
def mergeSort(data):
   
    if len(data) > 1:
        # Devided the array in two part
        mid = len(data)//2
        leftHalf = data[:mid]
        rightHalf = data[mid:]
       
        # Recursively call the same function
        mergeSort(leftHalf)
        mergeSort(rightHalf)

        i=0
        j=0
        k=0
       
        while i < len(leftHalf) and j < len(rightHalf):
            if leftHalf[i] < rightHalf[j]:
                data[k] = leftHalf[i]
                i=i+1
            else:
                data[k] = rightHalf[j]
                j=j+1
            k=k+1

        while i < len(leftHalf):
            data[k] = leftHalf[i]
            i=i+1
            k=k+1

        while j < len(rightHalf):
            data[k] = rightHalf[j]
            j=j+1
            k=k+1

numList = [5,8,1,6,3,7,2,4,9]
print('Before sort:')
print(numList)
# Calling 'mergeSort' function by passing number array
mergeSort(numList)
print('After sort:')
print(numList)