ari@eleazar.dartmouth.edu (Ari Halberstadt) (08/24/90)
1: qsort is not re-entrant. 2: qsort is 4 times slower than it needs to be. THINK C 4.0's implementation of qsort uses global variables. This means that there is no way to call qsort if an invocation of it is already running. For instance, say the comparison function did more than just compare the data, and decided that every 1000 times it is called it must output some data in sorted order. The comparison function would therefore call qsort, but this would invalidate the original call to qsort. This "feature" of THINK C's qsort is only a bug if the ANSI standard requires that qsort be re-entrant. I called Symantec last week, and the guy said he didn't know if this is a bug, but that he would check it. I haven't heard back from them yet. Another problem with THINK C's qsort is that it is around 4 times slower than it needs to be. Around one half of the time is spent making a totally unnecessary call to a function. The remaining extra time is spent making unnecessary checks on small subfiles. By adding an insertion sort on small subfiles combined with a median of three selection, I wrote a completely re-entrant version of quick sort that runs 4 times faster than THINK C's. Furthermore, this improved version will almost never exhibit quadratic behavior, and is fast even on presorted data. Even without any assembly language, this improved algorithm beats THINK C hands down. I wish Symantec would pay more attention to algorithms that anyone can find in a decent text book. This improved quick sort is a very small part of a set of freeware XFCNs which I am about to release (as soon as I can get them uploaded from my mac). --Ari ari@dartmouth.edu --