Shell Sort

Generalizes insertion sort to allow exchanges of elements far apart. Uses a decreasing sequence of gap values.

Best O(n log n) Avg O(n^(4/3)) Worst O(n^(3/2)) Space O(1) Stable No In-place Yes Comparison-based

How it works

Generalizes insertion sort to allow exchanges of elements far apart. Uses a decreasing sequence of gap values.

Implementation

      
 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 temp = arr[i], j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
} def shell_sort(arr):
    gap = len(arr) // 2
    while gap > 0:
        for i in range(gap, len(arr)):
            temp, j = arr[i], i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2 void shellSort(vector<int>& arr) {
  for (int gap = arr.size()/2; gap > 0; gap /= 2)
    for (int i = gap; i < (int)arr.size(); i++) {
      int temp = arr[i], j = i;
      while (j >= gap && arr[j-gap] > temp) {
        arr[j] = arr[j-gap]; j -= gap;
      }
      arr[j] = temp;
    }
} void ShellSort(int[] arr) {
  for (int gap = arr.Length/2; gap > 0; gap /= 2)
    for (int i = gap; i < arr.Length; i++) {
      int temp = arr[i], j = i;
      while (j >= gap && arr[j-gap] > temp) {
        arr[j] = arr[j-gap]; j -= gap;
      }
      arr[j] = temp;
    }
} void shellSort(int arr[], int n) {
  for (int gap = n/2; gap > 0; gap /= 2)
    for (int i = gap; i < n; i++) {
      int temp = arr[i], j = i;
      while (j >= gap && arr[j-gap] > temp) {
        arr[j] = arr[j-gap]; j -= gap;
      }
      arr[j] = temp;
    }
} 