Hi, I would like to add that: http://www.wordiq.com/definition/Quicksort
Quicksort takes average O(n*log(n)) but worst O(n*n) comparisons, and average O(log n) but worst O(n) stack (and no head)... So I increased stack size of SORT to 16k, which means that it can "sort" up to 700 (roughly) identical lines (worst case). For sorting 10000 lines from RBIL, even a tiny 6k stack was enough. I think there is no point in using 64k of stack just to be able to "sort" 3000 identical/unsortable lines of text, while this would on the other hand reduce the size of the biggest sortable file by those 48k of extra stack space. If you want some really huge files sorted, use CWSORT (-> DJGPP), which uses protected mode (not sure for which stack size it is compiled and whether DJGPP supports auto-growing stacks. I think default stack size for Turbo C is 4k and for DJGPP it is 512k in recent DJGPP versions :-)). A really strange workaround would be using near pointers to an array of far pointers to save DOS stack. Current SORT seems to use up to 24 bytes of stack per qsort recursion level (far pointers). That would also allow using COM file format again, and some fancy custom malloc scheme (SORT never uses free(), so malloc() can be simplified). This is left as an exercise to the reader. I am happy with sorting 700 identical lines or 10000 RBIL text lines with SORT 1.4 for now. Eric > http://www.clipx.net/ng/turboc/ng4686d.php Turbo C qsort()... > http://www.geocities.com/roryesperanza2/manuals/turboc20.txt Turbo C 2 handbook (600k)... > Remarks An implementation of "median of three" variant of quicksort of > algorithm. > http://www.sci.csuhayward.edu/~billard/cs3240/node32.html Quicksort and median-of-3... > http://www.azillionmonkeys.com/qed/sort.html Sort optimizations and caveats > http://www.devx.com/vb2themax/Tip/19472 Why median-of-3 might help http://www.cse.unsw.edu.au/~cs3121/03s2/exam/00midexam-solutions.html ... > http://encyclopedia.thefreedictionary.com/Quicksort ... ------------------------------------------------------- This SF.Net email sponsored by Black Hat Briefings & Training. Attend Black Hat Briefings & Training, Las Vegas July 24-29 - digital self defense, top technical experts, no vendor pitches, unmatched networking opportunities. Visit www.blackhat.com _______________________________________________ Freedos-devel mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/freedos-devel
