Re: C Sharp sorting considered superior to C by an order of magnitude

On Feb 25, 6:47 am, spinoza1111 <spinoza1...@xxxxxxxxx> wrote:
On Feb 25, 8:31 pm, Daniel Kraft <d...@xxxxxxxx> wrote:
spinoza1111 wrote:
Just for the sake of it, why did you only implement O(n^2) algorithms

Quicksort isn't O(n^2) it is O(n) for random data, and the O(n^2) case
is detectable O(n): so a fast quicksort is O(n).

I think you mean O(N log N). For random data, a comparison based
sorting algorithm can't break N log N as a lower bound.

Relevant Pages

  • Re: What is the most fast sorting algorithm?
    ... I think it is quicksort. ... I don't think any of these algorithms detect quadratic behavior. ... Introsort cuts off to heapsort when the stack ... "Using heapsort as the ``stopper'' yields a sorting algorithm that is just ...
  • Re: Whats more important optimisations or debugging?
    ... QuickSort is not theoretically slower than all NlogN algorithms. ... I meant the worst case complexity. ... This is one of the points about mergesort. ...
  • Re: Fastcode Sort B&V version 0.8
    ... > I don't think the benchmark should be aimed at specific algorithms. ... whether they be quicksort, shellsort or whatever. ... which will cause a slow running time or maximize the chance of running out ...
  • Re: Simple Sort - the smallest sorting routine?
    ... The innermost loop of quicksort is extremely tight: ... movl, %edx ... movl %r13d, %esi ... indirect_quick_sort, random data: 76us ...
  • Re: sorting algorithms
    ... >I was pondering over the general interest in sorting algorithms. ... happened over the past 10 years for quicksort, heapsort, inplace mergesort. ... But this is not general-purpose. ...