Merge Sort
Question:
Write a program to perform merge sort on [85,63,0,12,47,96,52]
Program:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
def mergeSort(alist): print("Splitting ",alist) if len(alist)>1: mid = len(alist)//2 lefthalf = alist[:mid] righthalf = alist[mid:] mergeSort(lefthalf) mergeSort(righthalf) i=0 j=0 k=0 while i < len(lefthalf) and j < len(righthalf): if lefthalf[i] < righthalf[j]: alist[k]=lefthalf[i] i=i+1 else: alist[k]=righthalf[j] j=j+1 k=k+1 while i < len(lefthalf): alist[k]=lefthalf[i] i=i+1 k=k+1 while j < len(righthalf): alist[k]=righthalf[j] j=j+1 k=k+1 print("Merging ",alist) alist = [85,63,0,12,47,96,52] mergeSort(alist) print(alist) |
Explanation:
Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.
Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
Splitting [85, 63, 0, 12, 47, 96, 52] Splitting [85, 63, 0] Splitting [85] Merging [85] Splitting [63, 0] Splitting [63] Merging [63] Splitting [0] Merging [0] Merging [0, 63] Merging [0, 63, 85] Splitting [12, 47, 96, 52] Splitting [12, 47] Splitting [12] Merging [12] Splitting [47] Merging [47] Merging [12, 47] Splitting [96, 52] Splitting [96] Merging [96] Splitting [52] Merging [52] Merging [52, 96] Merging [12, 47, 52, 96] Merging [0, 12, 47, 52, 63, 85, 96] [0, 12, 47, 52, 63, 85, 96] |
Leave a Reply