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.

  divide / sorted / merge

  merge / inserted / delete

  merge / divide / sorted

  merge / sorted / divide

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

  Parametering

  Quick Sorting

  Listing

  Merging

 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 greater than or equal to 10

  the length of the list is exactly 0.1

  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 / very small data sets

  less space / large data sets

  extra space / large data sets

  less space / small data sets

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

  There is no such thing

  A recursive algorithm is just an algorithm which uses a loop

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

  None of the above

 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

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

  Line 9 and 10

  Line 11 and 12

  Line 15 and 16

 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 …

  sort one small list

  sort one big list in the first place.

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

  Bill Gates

  John Von Neumann

  Alan Turing

  Monty Harvard

 12. The advantage of merge sorts include:

  Good for sorting data that is accessed sequentially

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

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

  All of the above

 13. Disadvantges of merge sort include:

  It uses recursion which takes up a lot of memory

  It is generally considered slower than the 'QuickSort' method

  All of the above

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

  TRUE

  FALSE