Shell sort in kotlin is the generalization of insertion sort which __overcomes the drawbacks of insertion sort__ by comparing elements separated by a gap of several positions.

Shell sort allows to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. **Last step of shell sort is ultimately insertion sort.**

In short, it improves insertion sort by comparison and exchange elements that are far away.

Shell sort uses a sequence that can be referred as increment sequence. **Shell sort makes multiple passes over array** and sort number of equally sized array using insertion sort.

- Basic principle of Shell sort is, Compare the first element with a element which a
**specific distance apart** - We can calculate the
**distance**based on various values like by dividing the array size by 2 (`size/2`

), or any other value - Once we get the distance, then we start comapring the elements. For example,

First element with an element with distance away, and second element with distance aways from second element, it goes so on. - While comparing the first element with a element at a distnce, we swap them only if the first element is larger than the element at the distance. Same applicable for all the elements
- Once we are done with first pass, hen we will go for seconds pass now we would be
**dividing the distnce**using the same logic that we used in first place - At end we will have distance as 1, so this pass acts as insertion sort by comparing the adjacent elements

Only for the first time, we will be using the array size for devision logic but after that we will be using the distance we got from previous pass.

- First, we got to decide on what based on what distance, we are going to perform the comparisions. I have choosen a gap/distance based on the
`array_size/2`

After first iteration we would be reduing the gapby dividing the previous gap by 2

```
var gap = n / 2
```

```
while (gap > 0)
```

```
var i = gap
while (i < n) {
```

`gap+1`

Swap value between the comparision when the smaller index has bigger value than value at larger index.

```
val temp = arr[i]
// shift earlier gap-sorted elements up until the correct location for a[i] is found
var j = i
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap]
j -= gap
}
// put temp (the original a[i]) in its correct
// location
arr[j] = temp
i += 1
```

```
gap /= 2
```

Complete code for shell sort in kotlin

```
/* function to sort array using shellSort in kotin*/
fun sort(arr: IntArray): Int {
val n = arr.size
// decide the gap, then reduce the gap
var gap = n / 2
while (gap > 0) {
// Do a gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already
// in gapped order keep adding one more element
// until the entire array is gap sorted
var i = gap
while (i < n) {
// add a[i] to the elements that
// have been gap sorted save a[i] in temp and make a hole at
// position i
val temp = arr[i]
// shift earlier gap-sorted elements up until
//the correct location for a[i] is found
var j = i
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap]
j -= gap
}
// put temp (the original a[i]) in its correct
// location
arr[j] = temp
i += 1
}
gap /= 2
}
return 0
}
fun main(args: Array<String>) {
val arr = intArrayOf(23, 12, 1, 8, 34, 54, 2, 3)
println("Array before sorting")
for( a in arr) print("$a ")
sort(arr)
println("Array after sorting")
for( a in arr) print("$a ")
}
```

We can also create shell sort for lists in koltin

```
fun MutableList<Int>.swap(index3: Int, index3: Int) {
val tmp = this[index3]
this[index3] = this[index3]
this[index3] = tmp
}
fun MutableList<Int>.shellSort(): MutableList<Int> {
var sublistCount = count() / 2
while (sublistCount > 0) {
var index = 0
outer@while (index >= 0 && index < count()) {
if (index + sublistCount >= count()) break
if (this[index] > this[index + sublistCount]) {
swap(index, index + sublistCount)
}
if (sublistCount == 1 && index > 0) {
while (this[index - 1] > this[index] && index - 1 > 0) {
swap(index - 1, index)
index -= 1
}
index++
} else {
index++
continue@outer
}
}
sublistCount /= 2
}
return this
}
fun main(args: Array<String>) {
var mutableListOfInt = mutableListOf(10, 4, 5, 2, 1, 3, 6, 9, 8, 7)
print(mutableListOfInt.shellSort().toString())
}
```