Patent US 5,535,378

The improved Quicksort method of the present invention utilizes two pointers initialized at opposite ends of the array or partition to be sorted and an initial partition value Pvalue located at the center of the array or partition. The value at each of the end pointers is then compared to Pvalue. Sorting is accomplished by recursing the partition process for the two array segments bounded on one side by the final P valve location. This method prevents excessive recursions, and allows the identical array case to recurse to the ideal minimum: Log2(N). Also, by relaxing the offsider criteria to include elements equal to Pvalue, the present invention presents arrays of two valves or a very small range of valves from recursing excessively. Further, the sorting method of the present invention may test the final position of the initial Pvalue to determine whether it is in the center (75%-95%) portion of the array or subarray being positioned. If it is not, the first Pvalue is disregarded, and a new initial Pvalue is selected, preferably randomly selected from the larger subarray bounded on one side by the final Pvalue location resulting from the initial attempt. This method prevents arrays situated in "pipe organ" sequence from recursing excessively. In addition, a maximum recursion depth limit may be specified to force section of a new initial Pvalue if a recursion level exceeds the depth limit.