Sorting Algorithms

We have recently learned about sorting algorithms in the class.

Here is a list of them:
-Insertion Sort
-Selection Sort
-Merge Sort
-Quicksort

Insertion and selection sort are pretty straightforward in how they work, but they both take O(n^2) time.
The last two are both divide-and-conquer algorithms that I have introduced in the past month. The main idea about them is dividing the input lists into halves and sorting these smaller parts. Afterwards, these parts are combined. For mergesort, the combination step is done by a helper function.
Both of the functions have the worst case runtime of O(nlogn).

A common method to find the runtime of divide and conquer algorithms is by using the Master Theorem. I will cite the Master Theorem (http://en.wikipedia.org/wiki/Master_theorem) from Wikipedia:

T(n) = a(Tn/b) + f(n) where a > 1 or a = 1, b > 1

• n is the size of the problem.
• a is the number of subproblems in the recursion.
• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)
• f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems.

1)If k < log_b{a}, then T(n) = O(nlog_b{a}).

2)If k = log_b{a}, then T(n) = O(nklog n).

3)f k > log_b{a}, then T(n) = O(nk).

Where k is the exponential of the asymptotic runtime of f(n)

Source: http://www.cs.toronto.edu/~liudavid/csc236/resources/notes.pdf

Now I will apply the Master Theorem on merge sort.

Merge sort:

- Divide the lists into halves

- Sort each of them seperately

- Merge the halves together

Define a function T(n) that represents the runtime of merge sort based on a list of size n. Then we can recursively define T(n) by using the given information above.

T(n) = 2T(n/2) + cn        (cn is a result of merging that costs linear time)

Now, let's compare this to the special form introduced above.
a = 2, b = 2, k = 1
Then we know that k = log_b{a}
Therefore we will be using 2)
Then T(n) = O(nlogn)

In my following blog post I will be talking more about efficiency and a sorting algorithm I have worked on with my friend.