User talk:TakuyaMurata/Barcelo's method

Carlos' method works, and for *some* inputs results in slightly better running times (note: the following assumes that the pivot value is the median of the first, MIDDLE and last elements, not the first, SECOND and last elements; using first, middle and second results in N*N running time if the input is already in order or in reverse order). Compared to an equivalent method using exchanging, Carlos' method is slightly faster if: - the input is in random order - the input is in REVERSE order But significantly slower if: - the input is already in order (or nearly so).

--james_barbetti@yahoo.com