Shell sort is an in-place sorting algorithm that improves upon the insertion sort by dividing the array into smaller subarrays called “shells.” It starts by sorting pairs of elements that are distant from each other by a specified gap. It then gradually reduces this gap until it becomes 1, effectively performing a final insertion sort on the nearly sorted array.

publicstaticvoidshellSortExchange(int[] arr) { int temp;

// Start with a gap, and gradually reduce it for (intgap= arr.length / 2; gap > 0; gap /= 2) { // Iterate through the array for (inti= gap; i < arr.length; i++) { // Compare and swap elements with a gap for (intj= i - gap; j >= 0; j -= gap) { if (arr[j] > arr[j + gap]) { temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } else { break; } } } } }

publicstaticvoidshellSortShift(int[] arr) { // Loop through different gap sizes, starting with half the array length for (intgap= arr.length / 2; gap > 0; gap /= 2) { // Iterate through the array elements for (inti= gap; i < arr.length; i++) { intj= i; // Store the current element's index inttemp= arr[j]; // Store the current element's value

// Compare the current element with elements at a specific gap if (arr[j] < arr[j - gap]) { // Shift elements to the right within the gap until the correct position is found while (j - gap >= 0 && temp < arr[j - gap]) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; // Place the current element in its correct position } } } }