# 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 $O(N^2)$ 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: