Why Strings as Classes?

[superdan]

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.