About the algorithm

The sort algorithm that was selected is a recursive merge sort. This sort needs a time which is strictly proportional to $n {}^2\!\log n$ and has, unlike quicksort, no bad behaviour for special cases. As often the compare of two lines can be rather slow (when comparing ranges of columns) it is important to minimize the number of compares, and also here a merge sort wins (quicksort has less overhead and therefore it can win in speed when the compare is trivial). The main drawback of the merge sort is that it needs some extra memory. In the case of stedi this is roughly 1.5 pointers per line to be sorted. This means that when there is no free memory the sort command cannot be executed. Stedi will give the message "no memory" and execution is aborted (for macro's).

Comparing ranges of columns is rather slow, because each time two lines are compared they have to be brought to screen representation. This isn't necessary for the other modes. It is impractical to work out all the lines first and then compare them. This could pose enormous memory requirements. If the user would like to speed up such sorting he could expand all tabs before the sorting command is given, do the sorting in the character mode, and then put the tabs back in. This can be done provided that the tabs are `trivial' (no essential blanks inside tabs as is sometimes the case with the first three characters in the fold lines, no strings of blanks inside character strings that have to be printed to the screen, etc.).