(algorithm)
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 ...)
bucket sort.
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.
Author: PEB
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 Black.
Entry modified 12 October 2010.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "distributive partitioning sort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 12 October 2010. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/distributivePartitioningSort.html