Lutger: > Am I right in thinking this algorithm basically requires random access? Both > the > C++ version and the D version will work for ranges that don't do that, but > the > performance difference won't matter anymore because it is likely crap anyway.
I don't think it's crap with a linked list, it can be slower, but not so much because the inner loop of algorithm doesn't need random access, it just just advances two cursors by one step each. There is a bit of wasted time before the inner loop, to set the right cursor at its right place, but it's a small number of steps compared to the whole O(n^2) play. I have not tried timed it with linked lists because SList isn't working yet. Bye, bearophile
