Question

Can someone help me with this problem? Given an unordered list of n numbers, what algorithm would you use to sort it, and what is the worst-case runtime of the algorithm?

Answer 1

what class is this?

Answer 2

Merge sort and n log n.
If you don't know what it is:

Merge sort is recursive. This means that with each step, you're not necessarily solving part of the problem, you're just turning it into an easier problem. So easy, that eventually you only need to sort a list of size 1. Once that's done, you combine all of your results and there's your final answer.

You have the merge sort function and the combine function. You call merge again once on the first half of the list, and then again on the second half of the list. Combine those results and you're finished.

But wait! If you call merge again, the process will simply repeat. It will keep dividing the list in half until it can't anymore! A base case must be included, which is when the list is already sorted (size 1, some other variations on this step though).

Combining is easy in this case because you're combining two lists that are already sorted. For example,

1, 3, 5 and 2, 4, 6.

You simply need to compare the first number of each list and add the smaller one to a result array (or whatever data type you wanna use).

Since comparing requires that you look at every single number, it has a run time of n. How many times do we run compare?

You run it every time the list is cut in half, so the question becomes: how many times can n be divided in half? The answer to that is log base 2 of n, because that's how many times it takes to get to one.

So, you're running a subroutine that runs in n a total of log n times. The running time is n log n.