Sorting and recursion

In class exercises
Create a w10-recursion subdirectory in your cs21/class directory and copy over my starting point files: 
    $ cd 
    $ cd cs21/inclass
    $ pwd
      /home/your_user_name/cs21/inclass

    $ mkdir w10-recursion        
    $ cd w10-recursion
    $ pwd
      /home/your_user_name/cs21/class/w10-recursion

    $ cp ~adanner/public/cs21/w10-recursion/* .
    $ ls
      mergesort.py   recursion.py
  1. Open recursion.py. We are going to write some iterative and recursive versions of the same function. Iterative versions use loops, recursive versions do not use loops, and instead contain calls to themselves. The idea of recursive functions is based on recursive definitions. For example, n! can be defined as n(n-1)!.
  2. Next, open mergesort.py. Merge sort is a faster sorting algorithm than selection sort. It uses the same type of divide and conquer strategy as binary search does. It is also an example of an elegant recursive solution.

    We are going to look at the mergeSort code together. Once we understand how the recursive calls work, you are going to come up with an algorithm for merging two sorted lists of size n into a sorted list of size 2n. Your merging algorithm should be iterative (not recursive). Once you have an algorithm, try coding it up in the merge function.