User talk:TakuyaMurata/Barcelo's method
From Wikipedia, the free encyclopedia
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