On Sun, May 1, 2022 at 1:44 PM Chris Angelico <ros...@gmail.com> wrote:
> On Mon, 2 May 2022 at 06:43, Dan Stromberg <drsali...@gmail.com> wrote: > > On Sun, May 1, 2022 at 11:10 AM Chris Angelico <ros...@gmail.com> wrote: > >> > >> On Mon, 2 May 2022 at 01:53, Nas Bayedil <nbaye...@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. -- https://mail.python.org/mailman/listinfo/python-list
