Re: Length-unaware sorting algorithm

[Coda Highland <chighland@...>]

On Thu, Aug 25, 2016 at 6:14 PM, Soni L. <fakedme@gmail.com> wrote:
>
>
> On 25/08/16 08:39 PM, Coda Highland wrote:
>>
>> On Thu, Aug 25, 2016 at 4:33 PM, Phil Bewig <pbewig@gmail.com> wrote:
>>>
>>> Insert items into a priority queue as they arrive. Extract the items from
>>> the priority queue after all the items have arrived.
>>>
>>>
>>> On Aug 25, 2016 6:19 PM, "Tim Hume" <tim@nomuka.com> wrote:
>>>>
>>>> Well I guess you could just grab data as they arrive and keep on
>>>> inserting
>>>> them into the correct position in a growing list of sorted data you've
>>>> already received? It might not be very efficient though.
>>>>
>>>> Cheers,
>>>>
>>>> Tim Hume
>>>>
>>>> On Thu, 25 Aug 2016, Soni L. wrote:
>>>>
>>>>> Have y'all noticed how pretty much all sorting algorithms rely on
>>>>> length?
>>>>>
>>>>> Are there any sorting algorithms that aren't explicitly aware of the
>>>>> sequence/array length, and instead just happen to produce a sorted
>>>>> array?
>>>>> (i.e. a sorting algorithm that doesn't rely on # or manual length
>>>>> calculations, and doesn't explicitly try to find the boundary where the
>>>>> array ends.)
>>>>>
>>>>> Even the current Lua sorting algorithm uses the table length. Would be
>>>>> interesting if there was a sorting algorithm about as fast as Lua's
>>>>> current
>>>>> sorting algorithm, but without relying on length.
>>>>>
>>>>>
>> Phil describes heapsort, and this is exactly the use case heapsort was
>> designed for.
>>
>> Tim describes insertion sort, which is less efficient than heapsort
>> but still better than it sounds on paper.
>>
>> Both are reasonable choices; insertion sort's simplicity of
>> implementation makes it attractive.
>>
>> /s/ Adam
>>
> 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.

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