Talk:Insertion sort

Question: Which language is the example implementation written in?

The example is written in Python. I'm planning on simplifying it a bit, in particular to remove the cmp function being passed as a parameter:

• A built-in function cmp() already exists, and means something different (-ve if a<b, 0 if a=b, +ve if a>b);
• IMO, Python's lambda notation and default arguments are not appropriate for near pseudo-code;
• "a > b" is much better for trying to understand an algorithm than a function call.
• Custom Python types can define their own comparisons anyway, so a comparator parameter is unnecessary.

--Carey Evans

Should heapsort be listed as type of insertion sort ? --Taw

No. Heapsort is more closely related to selection sort. --Damian Yerrick

Actually heapsort and insertion sort have a pretty close relation. In both, you are taking the elements of the list and successively inserting them into a data structure from which you can, at the end, extract the sorted sequence. In selection sort you actually search the unsorted elements; in these sorts you simply present the unsorted elements sequentially. Deco 05:54, 29 Mar 2005 (UTC)

Removed mergesort statement

I removed this statement:

This is even less than Merge sort for finite n, though both do O(n log n) comparisons.

Not only is this silly (you can't sort infinite lists in finite time, especially not with this sort) but it assumes that merge sort runs in exactly n log n time, rather than just Θ(n log n) time. The truth is that:

$\log n!=\log \prod _{i=1}^{n}i=\sum _{i=1}^{n}\log i.$

Now, we can bound it on both sides with integrals:

$n\log n-n+1=\int _{x=1}^{n}\log x<\sum _{i=1}^{n}\log i<\int _{x=1}^{n+1}\log x=(n+1)\log(n+1)-n$

So in fact log n! is $\Theta (n\log n)$, no different from mergesort (if we could somehow avoid the time for the swaps.) Deco 05:54, 29 Mar 2005 (UTC)