Preview

06 - 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 / divide / sorted

  merge / inserted / delete

  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>>

  Merging

  Listing

  Parametering

  Quick Sorting

 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 exactly 0.1

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

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

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

 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 ______________.

  less space / large data sets

  extra space / very small data sets

  less space / small data sets

  extra space / large data sets

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

  None of the above

  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

  There is no such thing

 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 11 and 12

  Line 15 and 16

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

  Line 9 and 10

 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)

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

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

  The merge operation places the items back into the original list (alist

  All of the above

 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 several million lists

  sort two large lists

  sort one small list

 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 ….

  Monty Harvard

  Alan Turing

  John Von Neumann

  Bill Gates

 12. The advantage of merge sorts include:

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

  Good for sorting data that is accessed sequentially

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

  All of the above

 13. Disadvantges of merge sort include:

  It is generally considered slower than the 'QuickSort' method

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

  All of the above

  It uses recursion which takes up a lot of memory

 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. ...

  TRUE

  FALSE


Report an error