Suppose you would like to sort n music files using a comparison-based sorting algorithm (i.e. no bucket sort), but you only have an old, unreliable computer, which you have nicknamed "Rustbucket".

Every time Rustbucket compares two music files, x and y, there is an independent 50 - 50 chance that it has an internal disk fault and returns the value -1, instead of the correct result of 1 for true or 0 for false, to the question, "x lessthanorequalto y?"

Otherwise, Rustbucket correctly performs every other kind of operation (including comparisons not involving music files).

Describe an efficient algorithm that can use Rustbucket to sort n music files correctly and show that your algorithm has expected running time that is 0 (n log n).