Why Strings as Classes?

[Christopher Wright]

superdan wrote:
> Christopher Wright Wrote:
> 
>> == Quote from Christopher Wright (dhasenan at gmail.com)'s article
>>> WRONG!
>>> Those sorting algorithms are correct. Their runtime is now O(n^2 log n)
>>> for this linked list.
>> My mistake. Merge sort, qsort, and heap sort are all O(n log n) for any list type
>> that allows for efficient iteration (O(n) to go through a list of n elements, or
>> for heap sort, O(n log n)) and O(1) appending (or, for heap sort, O(log n)). So
>> even for a linked list, those three algorithms, which are probably the most common
>> sorting algorithms used, will still be efficient. Unless the person who wrote them
>> was braindead and used indexing to iterate rather than the class's defined opApply.
> 
> sigh. your mistake indeed. just not where you thot. quicksort needs random access fer the pivot. not fer iterating. quicksort can't guarantee good runtime if pivot is first element. actually any of first k elements. on a forward iterator quicksort does quadratic time if already sorted or almost sorted.

You need to pick a random pivot in order to guarantee that runtime, in 
fact. And you can do that in linear time, and you're doing a linear scan 
through the elements anyway, so you get the same asymptotic time. It's 
going to double your runtime at worst, if you chose a poor datastructure 
for the task.