5 Mar 2007 fejj   » (Master)

fzort: I think you mean Binary Insertion Sort and not Bubble Sort. The idea would be to use another in-place sorting algorithm that doesn't get hit hard when attempting to sort a segment that may already be pre-sorted. No reason to use anything slower than you have to, and so Binary Insertion Sort fits nicely.

For historical reasons, a Binary Insertion Sort was probably also used to eliminate recursive function call overhead as well as stack overflows.

Note that while the binary search portion of the Binary Insertion Sort algorithm is recursive, since it is tail recursive, it can be implemented in such a way as to even avoid having to use an internal stack.

See the last implementation discussed here for an example on how to do that.

Thanks for the link too, btw, I will be sure to check that out later when I get home from work!

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!