# C/++/# Is this considered a valid sorting algorithm?

1. Dec 6, 2015

### SlurrerOfSpeech

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

Code (Text):

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
}

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;
}

2. Dec 6, 2015

### Samy_A

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

3. Dec 6, 2015

### Filip Larsen

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?

4. Dec 6, 2015

### 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).

5. Dec 6, 2015

### SlurrerOfSpeech

That makes a lot of sense! Great idea.

Code (Text):

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

6. Dec 6, 2015

### Samy_A

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

7. Dec 6, 2015

### 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.

8. Dec 7, 2015

### Svein

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

9. Dec 7, 2015

### D H

Staff Emeritus
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.