Bogo Sort is a joke algorithm that sorts a list by shuffling it until it becomes sorted. This is extremely inefficient, with an O(n!) time complexity. The algorithm runs like this: 1. Have a list, L 2. Shuffle the list 3. Check if the list is sorted. If not, repeat steps 2-3 until it becomes sorted. In pseudocode: FUNCTION bogoSort(arr) RETURNS array SHUFFLE(arr) WHILE not SORTED(arr) DO SHUFFLE(arr) END WHILE RETURN arr END FUNCTION A subset of this algorithm is called 'Miracle Sort', which literally checks if the list is sorted and then waits for divine intervention.
Proof: Assume that bogo sort returns an unsorted list once. This means that for some list, bogo sort does not return the correctly sorted list. This is impossible because each permutation has a 1/(n!) chance of being selected. This means that the chances of the list being sorted is 1 (almost certain). Therefore, Bogo Sort will work in any case.
