• Read about insertion sort from http://en.wikipedia.org/wiki/Insertion_sort. We will implement it in Python in our lab.

1. Create an array of 10 random integers
2. Start with an empty list
3. Choose the i-th element from the array and insert it into the appropriate position in the list
4. Repeat for all elements in the array
5. Copy the sorted list into an array and output it
6. Check that the resulting array is sorted

Solution

• Recall the merge sort algorithm that we implemented in class. We used recursion for our implementation.

1. Try to implement merge sort without recursion. This is quite tricky to do in practice. So think before you implement your algorithm. Do not look for solutions in Google!
2. Check that your algorithm is correct by running it on an array of 10 random integers.

Solution