Re: Length-unaware sorting algorithm
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: Length-unaware sorting algorithm
- From: "Soni L." <fakedme@...>
- Date: 2016年8月28日 07:37:02 -0300
On 27/08/16 10:07 PM, Coda Highland wrote:
On Thu, Aug 25, 2016 at 6:14 PM, Soni L. <fakedme@gmail.com> 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.