this is about the homework question with switch(x,y,z)-

i think that i have a better way to prove that quicksort with

order(x,y,z) is still nlogn (without using a tree). here is how. we

already have order(x,y) and we can assume that order(x,y) takes O(1).

also-

order(x,y,z) {

order(x,y);

order(y,z);

order(x,y);

}

Now because of that order(x,y,z) takes 3*O(1), also known as O(1).

because quicksort just does many order(x,y), and we just proved that

asymptotically order(x,y) == order(x,y,z), we can conclude that

quicksort (under order(x,y) ) == quicksort (under order(x,y,z) )

.