Shell Sort - Better than O(N^2)
Prerequisite Knowledge
Before reading this article, you should first learn:
One-Sentence Summary
Shell Sort is a simple improvement of Insertion Sort that increases the local orderliness of an array through preprocessing, breaking through the time complexity of insertion sort.
You can open the visualization panel, click the play button, and then use the speed up/slow down button to adjust the speed, allowing you to intuitively experience the process of Shell Sort:
It must be admitted that the concept of Shell Sort is challenging 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 every element spaced h intervals apart (or the number of elements between them is h-1) is in order.
This concept is difficult to describe clearly in words, so let's look at an example. For instance, when h=3, a 3-sorted array would look like this: