(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 approximating the median and 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 outline in the paper has a preparation 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 E. Black.
Entry modified 28 March 2006.
HTML page formatted Mon Sep 11 09:46:02 2006.
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. 28 March 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/distributivePartitioningSort.html
