Merged Sort

Merge Sorting

     Algoritma pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.

    Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.

 

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

• Pertama kali 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.

data=[68,90,78,44,34,20,100,56,34]
import time
start = time.time()
def mergesort(data):
    if len(data)<2 :
        return
    mid=len(data)//2
    left = data[:mid]
    right = data[mid:]
    mergesort(left)
    mergesort(right)
    i=0
    j=0
    k=0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            data[k]=left[i]
            i += 1
        else:
            data[k]=right[j]
            j += 1
        k += 1
    while i < len(left):
        data[k]=left[i]
        i += 1
        k += 1
    while j < len(right):
        data[k]=right[j]
        j += 1
        k += 1
        print("marging", data)
mergesort(data)
print(data)
tick = time.time()-start
print ('It took %.10f' % tick , 'seconds.')