Is this considered a valid sorting algorithm?

[SlurrerOfSpeech]

Let me know if I've invented a valid O(n) sorting algorithm.

public void Sort ( this List<T> L ) 
{
   // Check every second whether L is sorted
   // Given enough time, natural bit flips will eventually make L sorted
    while ( !L.IsSorted() ) Thread.Sleep(1000); 
}

public bool IsSorted ( this List<T> L ) 
{
    // Returns true or false depending on whether L is in ascending order
   for ( int i = 1, n = L.Length; i < n; ++i ) if ( L[i-1] > L[i] ) return false;
   return true;
}

 

[Samy_A]

Have you tested this sorting method, and does it actually work?
If so, can you explain the concept "natural bit flips"?

 

[Filip Larsen]

Let me know if I've invented a valid O(n) sorting algorithm.

No, not unless you use a very alternative definition of what "valid" means.

Assuming that you algorithm comprise of waiting for stray cosmic rays and other quantum phenomenon to flip bits and then hope luck will turn it into a sorted array, you may want to ask yourself some questions:

• How many times will IsSorted be called before the array is sorted? If we call that number M (and ignore the 1 sec sleep) the time-complexity of your algorithm is now O(M*N).
• If the likelihood of a single bit flip (uncorrected and undetected by the memory subsystem) is p, then what is the likelihood of a sequence of bit flips will produce a sorted array (that is, an array with the same elements as before, but now just in ordered sequence) relative to the likelihood of a different array.
• Can you express an average M as a function of p and N?
• Would your "algorithm" be faster if you instead of waiting for natural bit flips just inserted some random numbers here? Would that make sense?
• Do you know what a standard sorting algorithm look like?
• Can you see any qualitative difference between such an algorithm and what you are proposing?
• Have you read up on Bogosort? Even that algorithm have an advantage over yours, can you see what?

 

[Samy_A]

Thanks to @Filip Larsen (love the Tintin avatar) I now know what "natural bit flips" means.

But then the "algorithm" is not even theoretically correct, as it will stop (if it stops) when the array is sorted.
However, there is no reason to assume that the sorted array will be in any way connected to the original array (except for having the same length).

 

[SlurrerOfSpeech]

• Would your "algorithm" be faster if you instead of waiting for natural bit flips just inserted some random numbers here? Would that make sense?

That makes a lot of sense! Great idea.

public static void Sort ( this List<T> L )
{
    while ( !L.IsSorted() ) L.RearrageRandomly();
}

 

[Samy_A]

That would make it a O(n*n!) "algorithm", I think.

 

[FactChecker]

Rearranging randomly is almost the worst possible sorting algorithm. The only thing worst would be something that maliciously un-sorts it. You need to add something that will actively put it in order.

 

[Svein]

Let me know if I've invented a valid O(n) sorting algorithm.

With modern memories and hardware error checks, your algorithm would not terminate as long as the machine it is running on is working.

 

[D H]

Let me know if I've invented a valid O(n) sorting algorithm.

No, for two reasons. One is that this isn't a valid sorting algorithm. Secondly, this isn't an O(n) algorithm. It's O(n!), or worse.

Thread closed.