Definition: Step 1: find the median key. Step 2: distribute the n items into n/2 buckets linearly covering the interval from the minimum to the median and n/2 buckets linearly covering the interval from the median to the maximum. Step 3: compact the buckets, removing empty buckets. Recursively start again at step 1 for any bucket with multiple items. Linked lists are used to avoid moving items until a final phase and to avoid bucket overflows.
Generalization (I am a kind of ...)
Aggregate child (... is a part of or used in me.)
select kth element, linked list.
See also shuffle sort, histogram sort, linear probing sort.
Note: Shuffle sort estimates the distribution of the items to be sorted by examining the first n/8 items. Distributive partitioning sort estimates the distribution by linearly interpolating from the minimum to the median and from the median to the maximum. Histogram sort counts the number of items in each (fixed) interval. See the note at histogram sort on distributing according to a rank function R.
The implementation outlined in the paper has a preliminary step. The step finds the median and partitions around it, then sorts the lower half and the upper half with the defined algorithm.
Wlodzimierz Dobosiewicz, Sorting by Distributive Partitioning, Information Processing Letters, 7(1):1-7, January 1978.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 12 October 2010.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "distributive partitioning sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 12 October 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/distributivePartitioningSort.html