Shell Sort

Core idea

Shell Sort starts with large gaps between compared elements and gradually reduces those gaps to 1.

Each pass performs an insertion-like sort over elements that belong to the same gap sequence.

It is a classic optimization over insertion sort and a good example of how preprocessing can reduce later work.

// Это улучшенная сортировка вставками
// Идея в том, чтобы сортировать вставками в определенных промежутках.
// лучший случай O(n*log(n))
// O(n^2)

function shellSort (arr) {
 for (let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
   for (let i = gap; i < arr.length; i++) {
     let j = i;
     while (j >= gap && arr[j-gap] > arr[j]) {
       const tmp = arr[j];
       arr[j] = arr[j - gap];
       arr[j - gap] = tmp;
       j = j - gap;
     }
   }
 }

 return arr;
}