Shell sort is an algorithm that first sorts the elements far apart from each other and successively reduces the interval between the elements to be sorted. It is a generalized version of insertion sort. In shell sort, elements at a specific interval are sorted. The interval between the elements is gradually decreased based on the sequence used.
function shell(arr,n) {
for(let gap = Math.floor(n/2);gap >= 1;gap = Math.floor(gap/2)) {
for(let fwd = gap; fwd < n; fwd++) {
let toBeInserted = fwd;
for(let rev = fwd - gap;rev >= 0;rev -= gap) {
if(arr[rev] > arr[toBeInserted]) {
let temp = arr[rev];
arr[rev] = arr[toBeInserted];
arr[toBeInserted] = temp;
toBeInserted = rev;
}
else {
break;
}
}
}
}
return arr;
}
Best Case : Ω (n log(n))
Average Case : θ (n log(n))
Worst Case: O (n^2)
O(1)
** where n is the length of the array