lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On 27/08/16 10:07 PM, Coda Highland wrote:
On Thu, Aug 25, 2016 at 6:14 PM, Soni L. <> wrote:
Heapsort assumes there is a length. Insertion sort is just bad, nowhere near
quicksort, and it also iterates, effectively calculating a length.
Heapsort does not assume there is a length. Heapsort assumes you'll
consume the sorted data when you're ready to consume the sorted data.
At no time do you need to care about how long it is. Either there is
more data, or there is not more data.

I take that back. It seems that the most popular implementation* of heapsort assumes there is a length, but heapsort itself doesn't.

Insertion sort is one of the better of the O(n^2) sorting algorithms.
It's nowhere near as bad as you make it sound. And furthermore, it
calculates a length of ITS OWN content, but it does so independently
of any extrinsic notion of length -- it only needs to know how much
data it's been fed so far.

Strand sort doesn't need to know a length, either.

/s/ Adam

Strand sort is a mergesort variant? Never heard of it before, but it sounds interesting.

Disclaimer: these emails may be made public at any given time, with or without reason. If you don't agree with this, DO NOT REPLY.