You're replying to a comment by Huh....

Huh... Permalink
August 28, 2008, 16:52

The RandomizedPartition algorithm referred to from the previous lecture modifies the source data. This means that in the general case you would need to make a complete copy of the array argument.

Meanwhile, bin sorting at can be accomplished in linear time, which suggests an alternative approach for some cases: perform a bin sort against the list, then find the k-th value from that sorted list (this would be valid work when max(A) - min(A) was not significantly larger than length(A))

Reply To This Comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

Type the word "disk_89": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.