# 03 - Merge Sort

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.

TRUE

FALSE

2. Fill in the blanks to complete the sentences that describe a merge sort
```The key word of course is '________', so we are referring to bringing two
lists together. Conceptually, a merge sort works as follows :
First, ______ the unsorted list into n sublists, each containing
1 element (a list of 1 element is considered sorted). Then,
repeatedly merge sub lists to produce new _______ sublists until
there is only 1 sublist remaining.
This will be the sorted list.```

merge / inserted / delete

merge / divide / sorted

merge / sorted / divide

divide / sorted / merge

3. _______ is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list.
`Play around with the code for merge sort here>>`

Quick Sorting

Parametering

Merging

Listing

4. In a merge sort, if ______________ then we already have a sorted list and no more processing is necessary.

the length of the list is greater than zero and less than the length of the list

the length of the list is exactly 0.1

the length of the list is greater than or equal to 10

the length of the list is less than or equal to one,

5. Read the following excerpt and from what you know about merge sort,see if you can fill in the blanks
```It is important to notice that the mergeSort function requires
________ to hold the two halves as they are extracted with
the slicing operations. This can be a critical
factor if the list is large and can make this sort problematic
when working on ______________.```

extra space / large data sets

less space / small data sets

less space / large data sets

extra space / very small data sets

6. Merge sort is known as a recursive algorithm. What is a recursive function?

None of the above

There is no such thing

A recursive algorithm is an algorithm which calls itself with "smaller (or simpler)" input values, and which obtains the result

A recursive algorithm is just an algorithm which uses a loop

7. Can you spot the place in the code for merge sort where recursion is taking place (a function calling itself)
```def mergeSort(alist):

print("Splitting ",alist)

if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]

#recursion
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```

Line 9 and 10

Line 15 and 16

Line 11 and 12

There is no recursion in this program - there's no such thing!

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 into the original list (alist

merging the two smaller sorted lists into a larger sorted list.

All of the above

The merge operation places the items back one at a time by repeatedly taking the smallest item from the sorted lists

9. The idea behind merge sort is the insight that it is quicker to sort two small lists then merge them together, rather than …

sort one big list in the first place.

sort one small list

sort several million lists

sort two large lists

10. Merge sort can handle data being held on very slow sequential devices such as tape drives

FALSE

TRUE

11. Merge sort has been around a while, having been developed in 1945 by ….

John Von Neumann

Bill Gates

Alan Turing

Monty Harvard

12. The advantage of merge sorts include:

Good for sorting data that is received one item at a time

All of the above

Good for sorting slow-access data (e.g. tape drive or hard disc)

Good for sorting data that is accessed sequentially

13. Disadvantges of merge sort include:

It uses recursion which takes up a lot of memory

All of the above

It is generally considered slower than the 'QuickSort' method

If the list is n long then it needs 2 x n memory space

14. Read the following excerpt on one advantage of Merge sort and decide whether it is true or false
```If two equal valued items are in the list, then their relative locations
are preserved (this is called "sort-stable") i.e. if item A = "cat"
and item C = "cat" then the sorted list will have AC. Quicksort
does not always keep this order - it could be AC or CA```

TRUE

FALSE

15. Informally, stability (e.g. a stable sorting algorithm) means that equivalent elements retain their relative positions, after sorting
`Note: A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. ... `

FALSE

TRUE