Sorting algorithms which accept a random comparator

Question

Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the algorithm is a sorted list/array.

I am wondering though which sort algorithms would actually work with a comparator that is not an order relation (in particular one which returns a random result on each comparison). By "work" I mean here that they continue return a permutation of their input and run at their typically quoted time complexity (as opposed to degrading to the worst case scenario always, or going into an infinite loop, or missing elements). The ordering of the results would be undefined however. Even better, the resulting ordering would be a uniform distribution when the comparator is a coin flip.

From my rough mental calculation it appears that a merge sort would be fine with this and maintain the same runtime cost and produce a fair random ordering. I think that something like a quick sort would however degenerate, possibly not finish, and not be fair.

What other sorting algorithms (other than merge sort) would work as described with a random comparator?

---

1. For reference, a comparator is an order relation if it is a proper function (deterministic) and satisfies the axioms of an order relation:

   • it is deterministic: compare(a,b) for a particular a and b always returns the same result.
   • it is transitive: compare(a,b) and compare(b,c) implies compare( a,c )
   • it is antisymmetric compare(a,b) and compare(b,a) implies a == b

(Assume that all input elements are distinct, so reflexivity is not an issue.)

A random comparator violates all of these rules. There are however comparators that are not order relations yet are not random (for example they might violate perhaps only one rule, and only for particular elements in the set).

Answer 1

So basically, you want to know if there is any sorting algorithm which wouldn't degrade from its average case if given a compare function similar to:

int Compare(object a, object b) { return Random.Next(-1,1); }

... where Random.Next() is some method that will produce a randomly-generated integer between a specified inclusive lower and upper bound.

The answer is actually that most basic sorting algorithms will perform according to their average case, because they obey at least one of the following two conditions:

1. A comparison between two unique elements is never made twice in the sort, and/or
2. In each iteration of the sort, the correct position of at least one element is determined and so that element is never compared again.

For instance, SelectionSort iterates through the sub-list of unsorted elements, finds the "least" and/or "greatest" element (by comparing each one to the greatest so far), places it in its correct position and repeats. As a result, even with a non-deterministic comparator, at the end of every iteration the algorithm will have found a value that it thinks is least or greatest, swaps it with the element in the position it is trying to determine, and never considers that element again, thus it obeys Condition 2. However, an A and B can be compared multiple times during this process (as the most extreme example, consider several passes of SelectionSort on an array that's sorted in reverse order) so it violates Condition 1.

MergeSort obeys Condition 1 but not 2; as sub-arrays are merged, elements in the same sub-array (on the left or right side) are not compared to each other because it has already been determined that the elements on that side of the array are in order among themselves; the algorithm only compares the least unmerged element of each subarray to the other to determine which is lesser and should go next in the merged list. This means that any two unique objects A and B will be compared to each other a maximum of one time, but any given element's "final" index in the full collection is not known until the algorithm is complete.

InsertionSort obeys only Condition 1 as well even though its overall strategy and complexity looks more like SelectionSort. Each unsorted element is compared with sorted elements, greatest-first, until one is found that is less than the element under inspection. the element is inserted at that point, and then the next element is considered. The result is that the relative order of any A and B is determined by one comparison, and further comparisons between that A and B are never performed, but the final position of any element cannot be known until all elements are considered.

QuickSort obeys both Conditions. At each level, a pivot is chosen and arranged such that the "left" side contains elements less than the pivot and the "right" side contains elements greater than the pivot. The result of that level is QuickSort(left) + pivot + QuickSort(right) which basically means the position of the pivot element is known (one index greater than the length of the left side), the pivot is never compared to any other element after it has been chosen as a pivot (it may have been compared with previous pivot elements, but those elements are also known and are not included in any subarrays), AND any A and B that end up on opposite sides of the pivot are never compared. In most implementations of pure QuickSort, the base case is one element, at which point its current index is its final index and no further comparisons are made.

The only comparative sort I can think of that wouldn't obey either condition is a non-optimized BubbleSort. If the sort does not accept that the X greatest elements are in their proper place after running X passes, and/or uses a "double-check" pass to verify the list is sorted, the sort will only be considered "done" when the random comparator has returned -1 or 0 for every two adjacent elements in the list during a pass and thus no swaps were performed (an event which, if truly random, would occur with probability $(2/3)^{N-1}$; for a relatively small list of 25 elements, that's a one in 2000 chance, while for 100 elements the probability is 3.7*10^-18). As the maximum absolute value of the result of the comparator increases, the probability for any one comparison to return negative or zero decreases towards .5, making the chance to end the algorithm that much less likely (the chance of 99 coin flips all landing heads, which is basically what this boils down to, is 1 in 1.2*10³⁰)

EDIT A LONG TIME LATER: There are a few "sorts" designed specifically as examples of what not to do which incorporate a random comparator; perhaps the most famous is BogoSort. "Given a list, if the list is not in order, shuffle the list and check again". Theoretically it will eventually hit on the right permutation of values, just like the "non-optimized BubbleSort" above, but the average case is factorial-time (N!/2), and because of the birthday problem (after enough random permutations you become more likely to encounter duplicate permutations than unique ones) there is a nonzero possibility of the algorithm never completing to officially the algorithm is time-unbounded.

Answer 2

Any algorithm that compares the same two elements twice is not a very clever algorithm, and in particular such an algorithm would perform less well than the most common sorting algorithms (merge-sort, quicksort, bubble-sort, insertion-sort). Any algorithm that compares pairs of elements at most once has the same (average) runtime cost regardless of the behavior of the compare function, if greater-than and lesser-than are equally likely results. Otherwise, you can at least guarantee that the sorting algorithm does no worse than the worst-case running time, which is less than $O(n^2)$ for any decent sorting algorithm.

I believe that a more interesting question is how well such an algorithm would perform if the compare function only gave the right answer in, say, 90% of cases on average. By how well it would perform i mean to answer the question: "what is, on average, the number of misplaced items when sorting a list of size $n$ by this algorithm?"

---

Edit: The problem is more interesting as I first thought, so here's a further comment:

Suppose that your $compare$ function is fair, that is $compare(x,y)=true$ with probability $1/2$ and $false$ with probability also $1/2$. Recall the insertion sort (functional style) algorithm:

insert x [] = [x]
insert x y:ys = if x < y then x:y:ys
                else y:insert x ys

sort_aux l e = match l with
                 [] -> e
                 x:xs -> sort_aux xs (insert x ys)

sort l = sort_aux l []

The average running time of this algorithm is then $\sum_{k=1}^{n} f(k)$ where $n$ is the length of $l$ and $f(k)$ is the average running time of $insert$ on a list of length $k$, that is if we count only applications of $:$ as having cost (if we count destructions as well, the formula is similar).

Now for $compare$ as described above, this is quite small: the mean number of steps performed by the insertion is given by:

$$ \sum_{i=1}^{k} i 2^{-i} \leq \sum_{i=1}^{\infty}i 2^{-i} = 2$$

This gives an average running time of $O(2n)$ for insertion sort, which is significantly better than the $O(n^2)$ given by a "decent" comparison function.

It would be fun to work out the average running times for the different other algorithms given this uniform compare function.

Answer 3

Mergesort with a fair random comparator is not fair. I don't have a proof, but I have VERY strong empirical evidence. (Fair means uniformly distributed.)

module Main where

import Control.Monad
import Data.Map (Map)
import qualified Data.Map as Map
import System.Random (randomIO)

--------------------------------------------------------------------------------

main :: IO ()
main = do
  let xs = [0..9]
  xss <- replicateM 100000 (msortRand xs)
  print $ countFrequencies xss

msortRand :: [a] -> IO [a]
msortRand = msort (\_ _ -> randomIO)

countFrequencies :: (Ord a) => [[a]] -> [Map a Int]
countFrequencies [] = []
countFrequencies xss = foldr (\k m -> Map.insertWith (+) k 1 m) Map.empty ys : countFrequencies wss
  where
    ys = map head xss
    zss = map tail xss
    wss = if head zss == []
      then []
      else zss

--------------------------------------------------------------------------------

msort :: (Monad m) => (a -> a -> m Bool) -> [a] -> m [a]
msort (<) [] = return []
msort (<) [x] = return [x]
msort (<) xs = do
  ys' <- msort (<) ys
  zs' <- msort (<) zs
  merge (<) ys' zs'
  where
    (ys, zs) = split xs

merge :: (Monad m) => (a -> a -> m Bool) -> [a] -> [a] -> m [a]
merge (<) [] ys = return ys
merge (<) xs [] = return xs
merge (<) (x:xs) (y:ys) = do
  bool <- x < y
  if bool
    then liftM (x:) $ merge (<) xs (y:ys)
        else liftM (y:) $ merge (<) (x:xs) ys

split :: [a] -> ([a], [a])
split [] = ([], [])
split [x] = ([x], [])
split (x:y:zs) = (x:xs, y:ys)
  where
    (xs, ys) = split zs

Answer 4

A very much related question is answered in All Sorts of Permutations (Functional Pearl) by Christiansen, Danilenko and Dylus. They run a sorting algorithm in the list monad, which essentially simulates non-determinism, returning all permutations of a given input list. The interesting property is that each permutation is returned exactly once.

Quoting from the abstract:

...

In this paper we look at the combination of non-determinism and sorting in a different light: given a sorting function, we apply it to a non-deterministic predicate to gain a function that enumerates permutations of the input list. We get to the bottom of necessary properties of the sorting algorithms and predicates in play as well as discuss variations of the modelled non-determinism.

On top of that, we formulate and prove a theorem stating that no matter which sorting function we use, the corresponding permutation function enumerates all permutations of the input list. We use free theorems, which are derived from the type of a function alone, to prove the statement.