Everything about Shellsort
Sorting algorithm which uses multiple comparison intervals
Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be understood as either a generalization of sorting by exchange or sorting by insertion. The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: ShellsortA 5-minute orientation
- Pick up a classic book: Data structures and algorithm analysis in CThe most-reprinted book on the subject
- Read the landmark paper: Improved upper bounds on shellsortCited 26 times
- Go sideways: Insertion sortA closely related topic
- Go sideways: Sorting algorithmA closely related topic
📖 Definitions
Noun Alternative form of Shellsort.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Improved upper bounds on shellsort
A new upper bound for Shellsort
Randomized Shellsort
An analysis of (h, k, 1)-Shellsort
Analyzing variants of Shellsort
Short Note: Empirical study of the expected running time of Shellsort
A lower bound on the average-case complexity of shellsort
Shellsort with three increments
📚 Books worth reading
Data structures and algorithm analysis in CMark Allen Weiss · 1993
Data structures & algorithm analysis in JavaMark Allen Weiss · 1999
Data structures & algorithms in JavaRobert Lafore · 2003
Shellsort and sorting networksVaughan R. Pratt · 1972
Data structures using C++D. S. Malik · 2010
Selected papers on analysis of algorithmsDonald Knuth · 2000
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Insertion sort Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient…
- Sorting algorithm In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order…
- Proxmap sort ProxmapSort, or Proxmap sort, is a sorting algorithm that works by partitioning an array of data items, or keys, into a number of "subarrays" (termed buckets…
- Incompressibility method In mathematics, the incompressibility method is a proof method like the probabilistic method, the counting method or the pigeonhole principle. To prove…
- Quicksort Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in…
- Introsort Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance…
- Comparison sort A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or…
- Bucket sort Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted…