Hello guys,

Here is a simple introduction to sorting algorithms:

http://abdulapopoola./2012/02/03/sorting-algorithms/

Let me know what you think.

Very nice post.

Btw, regarding this:

"Interestingly, the insertion sort can be made to run in O(nlgn) time. Since the sublist in lower positions is always sorted; if a binary search is used to find the insertion point in this sub-list instead of linear search., the number of comparisons reduces to lg n."

Is this correct? I don't think so. You can spend O(log n) time figuring out where to insert using binary search, but you'll spend O(n) time to shift everything over right by one, no?

Cost of iteration i = Time to find out where x_i should go +  time to shift things over once I've done so.

Or are you imagining a data structure like a linked list where shifting over is cheap? I don't think you can do binary search on linked lists, right?

I think with merge sort, you may as well make your base case a bit higher. At least 2, and possibly bigger than that. No reason to go all the way down to size 1.

Regarding other comparison based algorithms, quicksort is probably the most popular. The default sorting algorithm for a lot of software.

Again, very nice post.

Heapsort is another one worth mentioning.

There are a bunch of non-comparison based sorting algorithms too. . . counting sort, radix sort. But for whatever reason these seem to be less popular (I guess because also less general than comparison based sorts.)

I suppose that you could do binary search on a linked list.


You'd build something like this:


           *
     /            \
/     \        /     \
/ \   /  \    /  \   /  \
1 2 3 4  5 6 7 15


And run binary search on it (I guess paying log(n) each time you want to grab any location from your list of #s?)

So you can get a binary search variant that probably runs in like log(n)^2 sort of time, I suppose? So n log(n)^2 running time for this variant of insertion sort you suggest.

Hrm, and you pay only O(n) to build the above data structure.

Hrm, none of this is precise, but now I'm starting to wonder if it can work. I'm not sure it works, because then when you want to insert say the number 8 into the above list, I feel like you have to rebuild the edges above the bottom level. Fix the edges so they point at the right person. this will take you again O(n) time.

So you'd again get an O(n^2) algorithm.

I don't think there is any way to do insertion sort even on linked lists in better than O(n log(n)).

Actually, you 100% cannot. There is a lower bound on the running time of comparison based sorting algorithms:

http://en.wikipedia.org/wiki/Comparison_sort#Lower_bound_for_the_average_number_of_comparisons

No comparison based sort can run in faster than n log(n) time (I assume this means worst running case time.)

Lol, late at night and I'm clearly losing it.

This:
"I don't think there is any way to do insertion sort even on linked lists in better than O(n log(n))."

should have been this:
"I don't think there is any way to do insertion sort even on linked lists in better than O(n^2)."

and the post after it shouldn't have been made, since it wasn't relevant.

Thanks ekt_bear.

I was looking at it from a purely theoretical perspective and not actually bothering about the cost of shifting operations.

All the same, thanks for your insight.

Hey ekt_bear

This is from the link you provided:

From Stirling's approximation we know that log 2(n!) is Ω(nlog 2n). This provides the lower-bound part of the claim.

So it is possible for a comparison based algorithm to run in nlogn.

abdulapopoola: Thing is, those shifting operations (or I guess insertions, as CS people would call them) are part of the theoretical consideration. It is expensive for me to insert() the number 8 into an arbitrary position into an array (since I have to shift everything over to the right by 1) but cheap to do this for a linked list (but then expensive for me to find() arbitrary positions in the list.)

This is part of the basic tradeoff when thinking about what data structure you want to use to represent a list of #s. . . for some applications an array is better, for others a LL is better.

Also, I agree that it is possible for comparison-based sorts to run in O(n log(n)). In fact all of the best ones that people use in practice run in this time (merge, quick, heapsort).

I forgot to mention that insertion sort carries out only swap operations (basically exchanging the pointers) and doesn't carry out shift operations.

Algorithms aside, it's been very very nice discussing with you and I am glad to have met you - thanks for your insight. It seems you are a C/C++ person; am I right?

Nope, I'm a Ruby person. . . I don't like C or C++ very much.

If I have the list

1 2 8 10 15 27 3 9 11

And I need to insert 3 in its proper position, I'll need to shift 8, 10, 15, 27 over. O(n) shifts, basically.

Likewise, nice to have met you too.