Accession Number:

ADA141583

Title:

Sorting by Recursive Partitioning,

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1983-12-01

Pagination or Media Count:

32.0

Abstract:

This document presents a new On lg lg n time sort algorithm that is more robust than On distribution sorting algorithms. The algorithm uses a recursive partition-concatenate approach, partitioning each set into a variable number of subsets using information gathered dynamically during execution. Sequences are partitioned using statistical information computed during the sort for each sequence. Space complexity is On and is independent from the order and distribution of the data. If the data is originally in a list, only Osquare root of n extra space is necessary. The algorithm is insensitive to the initial ordering of the data, and it is much less sensitive to the distribution of the values of the sorting keys than distribution sorting algorithms. Its worst-case time is On lg lg n across all distributions that satisfy a new fractalness criterion. This condition, which is sufficient but not necessary, is satisfied by any set with bounded length keys and bounded repetition of each key. If this condition is not satisfied, its worst case performance degrades gracefully to On lg n. In practice, this occurs when the density of the distribution over omegan of the keys is a fractal curve for sets of numbers whose values are bounded, or when the distribution has very heavy tails with arbitrarily long keys for sets of numbers whose precision is bounded. In some preliminary tests, it was faster than Quicksort for sets of more than 150 elements. The algorithm is practical, works basically in place, can be easily implemented and is particularly well suited both for parallel processing and for external sorting. Author

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE