Bogosort

Bogosort is a particularly ineffective sorting algorithm based on the generate and test paradigm. It is not useful for sorting, but may be used for educational purposes, to contrast it with other more realistic algorithms; it has also been used as an example in logic programming. If bogosort were used to sort a deck of cards, it would consist of checking if the deck were in order, and if it were not, throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted.

Worst case performance O(inf)
Best case performance O(n)
Average case performance O(n × n!)
Worst case space complexity O(n)

http://en.wikipedia.org/wiki/Bogosort