Posted by: atri | October 26, 2010

## Sorting in O(n log n) time

In today’s lecture, I mentioned that sorting $n$ numbers can be done in $O(n\log{n})$ time. There are multiple algorithms that can do this and we will see one, called merge sort later on in the course.

Below, I’ll describe the heap sort algorithm. All the ingredients are already there in Section 2.5 of the book. Below I’ll use notation from Pg. 64 in the text.

I’ll assume that the $n$ numbers are given as input in the array $A$ and that the algorithm will output the sorted numbers in array $B$.

1. $H\leftarrow {\tt StartHeap}(n)$.
2. For $i=1\dots n$
• ${\tt Insert}(H,A[i])$
3. For $i=1\dots n$
• $B[i]={\tt ExtractMin}(H)$.

The fact that this algorithm runs in time $O(n\log{n})$ follows from the run time complexities of the three procedures used above as mentioned on Pg. 64 of the book. The correctness of the algorithm also follows from the description of the procedures in the book.

As usual, if you have any questions, please use the comments section.

## Responses

1. […] we stated that you can sort the intervals in O(n log n) time (blog post regarding this found here) such that f(i) <= f(i+1) and that we can build the array s[1..n] in O(n) time such that s[i] is […]