Sorting

Sorting was the main topic for the week. We discussed Big-Oh runtimes of several sorting algorithms such as insertion sort, selection sort, etc., you know the rest! This was nothing new as I had already learned this in CSC108 and CSC165. But what was in fact new to me is merge and quick sort. Merge sort is the only sorting algorithm that I understand properly and that makes the most sense. So the concept consists of taking a list, splitting it in half (because of base 2, which requires in any runtime case log(n) steps) and then iterating over each element in order to sort (which requires in any case n steps). From this, we understand where the log(n) x n is derived from; since merge sort splits in half then iterates over the halves, we multiply n times log(n) due to the nested loop. The hardest part of this week would have been understanding these sorting algorithms by analyzing their codes. I think it was due to the fact that when I was first introduced to insertion, selection and bubble sort, their codes weren't written in simply one or two lines so it was easier to deduce where the runtime equations came from.