## Lecture 13 - Recursive Sorting

As usual, create a directory to hold today's activities:

$mkdir ~/cs170/labs/lab13$ cd ~/cs170/labs/lab13


## Divide and Conquer, or Sorting with Recursion

There's one sorting question I tend to hear a lot: "Is there a binary sort?" Well, the idea behind binary search finds its way into two different algorithms. These are Merge Sort and Quick Sort. They both approach the problem the same way as all of our other recursive functions: Break the problem into smaller portions, and build the overall solution from those smaller pieces.

Lab Activity 1
Merge Sort

Merge sort is probably the closest to a "binary" sort as you will get. Merge sort simply splits the list into two halves, and recursively calls Merge sort on both halves. Onces it gets the two sorted halves, it simply merges the two together to form a sorted list.

#### Details

Copy your sorting.py file from lab9 into this directory:

$cd ~/cs170/labs/lab13/$ cp ../lab9/sorting.py .


Create a function called merge_sort(a_list, start, end), which takes a list of integers, as well as two integers representing the beginning and end of the portion of the list to be sorted. The end value is exclusive. This function should not return anything, it should sort a_list in place. They discussed this modification of the algorithm in the reading.

#### Example

>>> my_list = [5, 4, 3, 2, 1]
>>> merge_return_value = merge_sort(my_list, 0, len(my_list))
>>> print(merge_return_value)
None
>>> print(my_list)
[1, 2, 3, 4, 5]


#### Hint

• Your base case for merge sort is when the number of elements in the current portion of the list is exactly one. A list of one element is sorted. A list of exactly one item is a list where the start is one less than the end.
• The book wrote the entirety of merge sort in one function. As I showed you today in lecture, it is easier to understand merge sort if you write one helper function. You should write a function called merge(a_list, start, end). This function takes a list of comparable items, and two integers start and end. It does not return anything: It sorts the items in place in a_list

You will use start and end to denote the two halves of the list. The middle index of the list denotes the beginning of the second half of the list. All you need to do is to compare the elements at the beginning of each half of the list. If they are out of order, swap them and move on to the next elements. The easiest way to accomplish this is to make a copy of the left and right halves of this list, and place the correct values back into the original list.

One thing you need to be careful about in the merge procedure is that you could easily run out of items in one list before the other. You need to make sure you gracefully handle this situation.

• Your merge_sort function should recursively call merge sort on each half of the list, then merge the two halves together.

### Challenge

After today's lecture, it should be quite apparent that Merge sort should run SIGNIFICANTLY faster than Insertion or Selection sorts. However, this is only observable after the list sizes get really, really large.

Copy the insertion sort function from the textbook into your program. Then, write a function test_sorts(a_list), which runs both insertion sort and and merge sort on the same list. Put print statements inside of this function, so you know when each algorithm begins and ends.

Using this function, find the size of list required to make insertion sort take a noticable amount of time, yet merge sort is still instant. What is this list size? Does the computer you are running on affect this output? Write your answers to these questions in the comments of your file. Be prepared to defend your answers.

#### Submission

When you have finished, create a tar file of your lab13 directory. To create a tar file, execute the following commands:

cd ~/cs170/labs
tar czvf lab13.tgz lab13/

To submit your activity, go to inquire.roanoke.edu. You should see an available assignment called Lab Assignment 13. Make sure you include a header listing the authors of the file.