Loading ...
Sorry, an error occurred while loading the content.
 

Re: Pentatonic mode and a solution to the order of the primes...

Expand Messages
  • Jens Kruse Andersen
    ... Sorting is provably O(n log n) and no better _if_ it is only based on comparing 2 elements at a time, e.g. with
    Message 1 of 5 , Feb 11, 2005
      > BTW, is it really linear? I've always thought sorting was O(n log n),
      > although some people described supposedly O(n) sorts but there
      > always seemed to be some sort of catch.

      Sorting is provably O(n log n) and no better _if_ it is only based on
      comparing 2 elements at a time, e.g. with <.

      If something useful is known about the elements, e.g. so they can easily be
      divided into certain subsets, then sorting often becomes O(n).

      Sorting integers is linear if the bits (or digits) can be extracted in linear
      time.
      With bits, the numbers can be placed in a binary tree with 0=left and 1=right
      in linear time. The sorted numbers can then be read in linear time by
      traversing the tree.

      Alphabetic sorting is linear if the letters can be extracted. E.g. place words
      in a tree with 26 children for each node.

      Sorting floats is linear e.g. if the binary representation can be recovered
      and understood. Then the mantissa and exponent can be sorted separately.

      In practice on typical sizes, linear sorting algorithms may often turn out
      slower or require more space than practical.

      --
      Jens Kruse Andersen
    Your message has been successfully submitted and would be delivered to recipients shortly.