6. Shell Sort

Ok, the last three algorithms were boring and slow, $O(n^2)$? Seriously that's awful! So, let's look at more efficient algorithms like shell sort which is a variation of insertion sort. Rather than comparing adjacent elements, we will compare elements from that are farther away from each other. We compare and sort items that are $K$ locations apart by using insertionSort subarrays of the original array that are $K$ locations apart. We gradually reduce $K$ from to $K=1$ (straight insertionSort), ending with a sorted array.

public <T extends Comparable<? super T>> void shellSort(T[] array) {
    for (int gap = array.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < array.length; i++) {
            int temp = array[i];

            int j = i;

            for(; j >= gap && array[j - gap].compareTo(temp) > 0; j -= gap) {
                array[j] = array[j - gap];
            }

            array[j] = temp;
        }
    }
}

Shell sort runs in $O\left(n^{\frac{3}{2}}\right)$ (when gap is odd) or more precisely $O(nlog^2(n))$ which is better than bubble, insertion, or selection, but still not the best. With space complexity of $O(1)$.

Next Page →