1. The Merge sort algorithm is also called the "divide and conquer" algorithm and its main focus is on how to combine together two pre-sorted arrays such that the resulting array is also sorted.
2. Fill in the blanks to complete the sentences that describe a merge sort
3. _______ is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list.
4. In a merge sort, if ______________ then we already have a sorted list and no more processing is necessary.
5. Read the following excerpt and from what you know about merge sort,see if you can fill in the blanks
6. Merge sort is known as a recursive algorithm. What is a recursive function?
7. Can you spot the place in the code for merge sort where recursion is taking place (a function calling itself)
8. Analyse the code below and explain what is happening in lines 11 - 31
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 = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)
The merge operation places the items back one at a time by repeatedly taking the smallest item from the sorted lists
merging the two smaller sorted lists into a larger sorted list.
All of the above
The merge operation places the items back into the original list (alist
9. The idea behind merge sort is the insight that it is quicker to sort two small lists then merge them together, rather than …
10. Merge sort can handle data being held on very slow sequential devices such as tape drives
11. Merge sort has been around a while, having been developed in 1945 by ….
12. The advantage of merge sorts include:
13. Disadvantges of merge sort include:
14. Read the following excerpt on one advantage of Merge sort and decide whether it is true or false
15. Informally, stability (e.g. a stable sorting algorithm) means that equivalent elements retain their relative positions, after sorting