Shell Sort - Better than O(N^2)
Prerequisite Knowledge
Before reading this article, you should first learn:
Summary in One Sentence
Shell sort is a simple improvement based on Insertion Sort, which increases the local order of an array through preprocessing, breaking the time complexity of insertion sort.
You can open the visualization panel, click the play button, and then use the speed up/slow down buttons to adjust speed, allowing you to intuitively feel the process of shell sort:
It must be acknowledged that the idea behind shell sort is difficult to conceive. I first learned about this algorithm in "Algorithms 4" and was amazed by how such a simple optimization could significantly enhance insertion sort.
First, we need to clarify the concept of an h
-sorted array.
h
-Sorted Array
An array is h
-sorted if any elements spaced h
apart (or with h-1
elements in between) are in order.
This concept is difficult to describe clearly with words, so let's look at an example. For instance, when h=3
, a 3
-sorted array looks like this: