tag

#distribution-sorting

6 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Histogram Sort

Histogram Sort Histogram sort constructs a frequency histogram over the key domain and uses it to reconstruct the sorted sequence. It generalizes counting sort to cases where the domain may be sparse or where counts are derived from a histogram structure. It appears in data processing pipelines where histograms are already computed or where frequency aggregation is natural. Problem Given an array $A$ of $n$ elements with keys drawn from...
algorithms sorting distribution-sorting histogram-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Uniform Bucket Sort

Uniform Bucket Sort Uniform bucket sort is a specialization of bucket sort where elements are assumed to be uniformly distributed over a known interval. Buckets are defined with equal width, and a direct arithmetic mapping assigns each element to a bucket. The design goal is to keep bucket sizes balanced so that each bucket remains small and can be sorted quickly. Problem Given an array $A$ of $n$ values drawn...
algorithms sorting distribution-sorting bucket-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Bucket Sort

Bucket Sort Bucket sort partitions elements into a set of buckets based on their value, then sorts each bucket separately and concatenates the results. It is effective when input values are uniformly distributed over a known range. Problem Given an array $A$ of $n$ elements drawn from a range $[a, b)$, sort the elements. Idea Divide the range into $k$ equal sized intervals Place each element into its corresponding bucket...
algorithms sorting distribution-sorting bucket-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Spreadsort

Spreadsort Spreadsort is a hybrid sorting algorithm that combines ideas from radix sort and comparison-based sorting. It partitions data based on key ranges and recursively sorts partitions, switching to comparison sorting when partitions become small or distribution becomes irregular. It is designed to achieve near linear performance on structured data while retaining robustness on arbitrary inputs. Problem Given an array $A$ of sortable keys, possibly integers, floating point values, or...
algorithms sorting distribution-sorting spreadsort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Pigeonhole Sort

Pigeonhole Sort Pigeonhole sort is a direct address sorting algorithm for integers in a small contiguous range. It creates one slot, or pigeonhole, for each possible key value, places elements into their matching slot, then scans the slots in order to rebuild the sorted array. It is close to counting sort, but the usual presentation stores the actual elements in holes rather than only their counts. Problem Given an array...
algorithms sorting distribution-sorting pigeonhole-sort
Wiki › Algorithms › 01. Searching and Sorting › 8. Integer and Distribution Sorting ›

Flashsort

Flashsort Flashsort is a hybrid distribution sorting algorithm that first classifies elements into buckets using an approximate linear mapping, then refines the partially ordered array using insertion sort. It is designed for datasets that are approximately uniformly distributed, where it can achieve near linear performance. Problem Given an array $A$ of $n$ elements, sort the array efficiently by exploiting approximate distribution information. Idea Flashsort has two main phases: Classification phase...
algorithms sorting distribution-sorting flashsort