Shell Sort Algorithm in Scala

1. Introduction

Shell Sort is a generalization of Insertion Sort, introducing the concept of interval h-sorting. It allows swapping of elements that are far apart, resulting in a faster initial placement of elements. The efficiency of the algorithm is derived from the fact that it performs sorting in multiple passes with diminishing intervals, until it finally performs a 1-sort, which is essentially Insertion Sort.

2. Implementation Steps

1. Choose an interval h for the initial pass. There are multiple ways to choose or calculate these intervals, with one popular choice being the use of Knuth's formula: \( h = 3h + 1 \).

2. Sort the elements h distance apart for the entire list. This creates h interleaved lists.

3. Reduce h and repeat the sorting until h becomes 1, at which point the algorithm becomes a simple Insertion Sort but is efficient because the list is already well-partitioned.

3. Implementation in Scala

object ShellSort {
  def sort(arr: Array[Int]): Unit = {
    val n = arr.length
    var h = 1
    while (h < n / 3) h = 3 * h + 1  // Using Knuth's formula
    while (h >= 1) {
      for (i <- h until n) {
        var j = i
        val tmp = arr(j)
        while (j >= h && arr(j - h) > tmp) {
          arr(j) = arr(j - h)
          j -= h
        }
        arr(j) = tmp
      }
      h /= 3
    }
  }
}
// Client code to test the shell sort algorithm
val array = Array(12, 34, 54, 2, 3)
ShellSort.sort(array)
println(array.mkString(", "))

Output:

2, 3, 12, 34, 54

Explanation:

1. We begin by calculating the initial interval or gap h using Knuth's formula.

2. Once the interval is defined, we start h-sorting the array. This involves looking at every hth element and performing insertion sort for elements at that gap.

3. As elements are h-sorted, they are not in their final positions, but they are closer to their final positions than they were.

4. After each pass, the value of h is reduced (in our implementation, we simply divide it by 3), and the h-sorting process is repeated.

5. As h approaches 1, the algorithm essentially becomes the Insertion Sort. However, the difference is that the list is much better partitioned at this point, making Insertion Sort efficient.