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.

Advertisements

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 […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: