Overview / Logistics

Sorting is an extremely important subroutine in many algorithms. We have taken it for granted so far, but we will now dive more into algorithms for performing sorting.

The code below generates a list of 20 elements between 0 and 100 and uses numpy's built in sorting algorithm to sort them. The "seed" is so that the random array that's generated will be repeatable for when you're debugging algorithms. If you change the seed, you'll get a different array

Your task in this exercise will be to devise and implement your own idea of a sorting algorithm. You may have seen algorithms before, but I want you to try to think from scratch about what you would do to take elements that aren't necessarily in order and to move them around. It doesn't have to be fancy! But you should first write out some pseudocode, then create a method which takes as input a list of numbers and which returns a list with the same elements in sorted order. Finally, what is the time complexity of your algorithm, in big-O notation?