new sorting algorithm

[Dan Stromberg]

On Sun, May 1, 2022 at 1:44 PM Chris Angelico <rosuav at gmail.com> wrote:

> On Mon, 2 May 2022 at 06:43, Dan Stromberg <drsalists at gmail.com> wrote:
> > On Sun, May 1, 2022 at 11:10 AM Chris Angelico <rosuav at gmail.com> wrote:
> >>
> >> On Mon, 2 May 2022 at 01:53, Nas Bayedil <nbayedil at gmail.com> wrote:
> >> > We believe that using this method to develop completely new, fast
> >> > algorithms, approaching the speed of the famous *QuickSort*, the
> speed of
> >> > which cannot be surpassed, but its drawback can be circumvented, in
> the
> >> > sense of stack overflow, on some data.
> >>
> >> Hmm, actually TimSort *does* exceed the speed of quicksort for a lot
> >> of real-world data. For instance, if you take a large sorted list,
> >> append a handful of (unsorted) items to it, and then sort the list,
> >> TimSort can take advantage of the fact that the bulk of the list is
> >> sorted. It ends up significantly faster than re-sorting the entire
> >> list.
> >
> >
> > In fact, Timsort is O(n) for already-sorted data, while many quicksorts
> are O(n^2) for already-sorted data.
> >
> > Quicksort can be salvaged by using a median-of-3 partitioning, but it's
> still O(n^2) in the (less common) worst case.
> >
>
> This is true, but purely sorted data isn't a very practical case. The
> case of mostly-sorted data IS practical, though, so it's a quite big
> win that it can be close to O(n), and still faster than inserting each
> item individually.
>

You seem to be of the impression that nearly-sorted data isn't an uphill
battle with a straightforward quicksort.

I'm having a hard time convincing myself of that.