Algorithm Speed (2.00) :

Array Size (100) :

Shell Sort :

Author(s) : Donald Shell Date : 1959

Shell sort is an improvement over insertion sort, introducing the concept of gaps (distances between elements compared during insertion). It iterates through the array, comparing elements at certain gap intervals and performing swaps if necessary. The initial gap typically starts large, allowing elements far apart in the array to be compared and potentially swapped, promoting a more sorted state. Gradually, smaller gaps are used, refining the sorted order until a gap of 1 is reached, effectively performing a standard insertion sort.

Time Complexity	O(n⁴/³)
Best Case	O(n log n)
Worst Case	O(n³/²)
Space Complexity	O(1)
Stable	No

def shellsort(arr):
	n = len(arr)
	# Define the gap sequence (here, Knuth's sequence)
	gap = n // 2
	while gap > 0:
		# Do an insertion sort for each sub-array with size gap
		for i in range(gap, n):
		# The first element (arr[i]) is already in its place
		temp = arr[i]
		j = i
		while j >= gap and arr[j - gap] > temp:
			arr[j] = arr[j - gap]
			j -= gap
		arr[j] = temp
		gap //= 2

# Test array
arr = [12, 34, 54, 2, 12, 90]
shellsort(arr)
print('Sorted array is:', arr)

function shellsort(arr) {
	let n = arr.length;
	// Define the gap sequence (here, Knuth's sequence)
	let gap = Math.floor(n / 2);
	while (gap > 0) {
		// Do an insertion sort for each sub-array with size gap
		for (let i = gap; i < n; i++) {
		// The first element (arr[i]) is already in its place
		let temp = arr[i];
		let j = i;
		while (j >= gap && arr[j - gap] > temp) {
			arr[j] = arr[j - gap];
			j -= gap;
		}
		arr[j] = temp;
		}
		gap = Math.floor(gap / 2);
	}
}

// Test array
let arr = [12, 34, 54, 2, 12, 90];
shellsort(arr);
console.log('Sorted array is:', arr);

public static void shellsort(int[] arr) {
	int n = arr.length;
	// Define the gap sequence (here, Knuth's sequence)
	int gap = n / 2;
	while (gap > 0) {
		// Do an insertion sort for each sub-array with size gap
		for (int i = gap; i < n; i++) {
		// The first element (arr[i]) is already in its place
		int temp = arr[i];
		int j = i;
		while (j >= gap && arr[j - gap] > temp) {
			arr[j] = arr[j - gap];
			j -= gap;
		}
		arr[j] = temp;
		}
		gap /= 2;
	}

	// Test array
	int[] arr = {12, 34, 54, 2, 12, 90};
	shellsort(arr);
	System.out.println("Sorted array is:" + java.util.Arrays.toString(arr));
}

func shellsort(arr []int) {
	n := len(arr)
	// Define the gap sequence (here, Knuth's sequence)
	gap := n / 2
	for gap > 0 {
		// Do an insertion sort for each sub-array with size gap
		for i := gap; i < n; i++ {
		// The first element (arr[i]) is already in its place
		temp := arr[i]
		j := i
		for j >= gap && arr[j-gap] > temp {
			arr[j] = arr[j-gap]
			j -= gap
		}
		arr[j] = temp
		}
		gap /= 2
	}

	// Test array
	arr := []int{12, 34, 54, 2, 12, 90}
	shellsort(arr)
	fmt.Println("Sorted array is:", arr)
}

void shellsort(int arr[], int n) {
	// Define the gap sequence (here, Knuth's sequence)
	int gap = n / 2;
	while (gap > 0) {
		// Do an insertion sort for each sub-array with size gap
		for (int i = gap; i < n; i++) {
		// The first element (arr[i]) is already in its place
		int temp = arr[i];
		int j = i;
		while (j >= gap && arr[j - gap] > temp) {
			arr[j] = arr[j - gap];
			j -= gap;
		}
		arr[j] = temp;
		}
		gap /= 2;
	}

	// Test array
	int arr[] = {12, 34, 54, 2, 12, 90};
	int n = sizeof(arr) / sizeof(arr[0]);
	shellsort(arr, n);
	printf("Sorted array is: ");
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
}