Everything about Smoothsort
Comparison-based sorting algorithm
In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of O(n log n) operations (see big O notation). Like heapsort, smoothsort is not a stable sort. The advantage of smoothsort is that it comes closer to O(n) time if the input is already sorted to some degree, whereas heapsort averages O(n log n) regardless of the initial sorted state. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: SmoothsortA 5-minute orientation
- Read the landmark paper: Smoothsort, an alternative for sorting in situCited 54 times
- Go sideways: HeapsortA closely related topic
- Go sideways: Weak heapA closely related topic
đź“– Definitions
Noun A sorting algorithm based on heapsort but using the Leonardo numbers, tending to perform better than heapsort in cases where the items to be sorted are already partially sorted.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
đź“š Books worth reading
Open Library didn't respond; try again in a moment.
đź”— Related topics
- Heapsort In computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each…
- Weak heap In computer science, a weak heap is a data structure for priority queues, combining features of the binary heap and binomial heap. It can be stored in…
- Heap (data structure) In computer science, a heap is a tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is the parent node…
- Binary heap A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary…
- Adaptive heap sort In computer science, adaptive heap sort is a comparison-based sorting algorithm of the adaptive sort family. It is a variant of heap sort that performs…
- K-way merge algorithm In computer science, k-way merge algorithms or multiway merges are a specific type of sequence merge algorithms that specialize in taking in k sorted lists…
- Binomial heap In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap)…
- Treap In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain…