Shell Sort is one of the oldest sorting algorithms and it's an extension of the Insertion Sort. This algorithm is fast and easy to implement, but it's hard to measure its performances.
Unlike Insertion Sort, Shell Sort starts by comparing the elements distant from each other by a certain gap that gets progressively decreased. By starting with the most distant elements, it can optimize performances as it's not limited by just comparing two adjacent elements.
O(n × log n)
|Best Case||O(n × log n)|