More sorting adventures

This past week we continue to learn about various types of sorting. Reading over the slog entries of classmates, it seems that most people have grasped this concept, especially those taking csc165 this semester, as we are also learning this topic in that class. I feel that the algorithms that have an average run-time of O(n^2) are generally easier to understand. I found that in most cases O(n^2) algorithms tend to use for loops inside for loops, as in selection sort. The algorithms that have an average run-time of O(n log n) are a little harder to understand. Some examples are merge sort and quick sort. The general idea of theses O(n log n) algorithms are to divide the array into smaller arrays and those arrays into even smaller arrays.These types of algorithms make use of recursion to sort the array.

One problem I have is understanding how a recursive algorithm would have a run-time of O(n log n). Another question I have is why sorting recursively would result in a shorter run-time compared to something like O(n^2) run-time. If any classmates reading this could explain I’d appreciate it!