# 1. Introduction

*Insertion Sort* is a simple and intuitive comparison-based sorting algorithm. The main concept behind insertion sort involves imagining a card game where each card is picked and placed in its correct position. Similarly, in insertion sort, the list is divided into a sorted and an unsorted part. We pick one element from the unsorted part and insert it into its correct position in the sorted sublist.

# 2. Implementation Steps

1. Start from the second element (assume the first element is sorted).

2. Compare the current element with the previous elements.

3. If the current element is smaller than the previous one, compare it with the elements before the previous one.

4. Repeat the process until the correct position is found for the current element or it reaches the beginning of the list.

5. Insert the element in its correct position.

6. Repeat the process for all elements in the list.

# 3. Implementation in Scala

```
object InsertionSort {
def sort(arr: Array[Int]): Array[Int] = {
for (i <- 1 until arr.length) {
val key = arr(i)
var j = i - 1
// Move elements of arr[0..i-1] that are greater than key
// to one position ahead of their current position
while (j >= 0 && arr(j) > key) {
arr(j + 1) = arr(j)
j = j - 1
}
arr(j + 1) = key
}
arr
}
}
```

### Client Code:

```
val arr = Array(12, 11, 13, 5, 6)
println("Original Array: " + arr.mkString(", "))
val sortedArr = InsertionSort.sort(arr)
println("Sorted Array: " + sortedArr.mkString(", "))
```

### Output:

Original Array: 12, 11, 13, 5, 6 Sorted Array: 5, 6, 11, 12, 13

### Explanation:

1. *object InsertionSort*: This is the singleton object for the *Insertion Sort* algorithm in Scala.

2. *sort(arr: Array[Int])*: The method performing the insertion sort on an array of integers.

3. *for (i <- 1 until arr.length)*: Looping from the second element to the last.

4. *val key = arr(i)*: Storing the current element whose left side is checked for its correct position.

5. *var j = i - 1*: Initializing the variable *j* which is used to traverse the sorted part of the array.

6. *while (j >= 0 && arr(j) > key)*: If *j* is a valid index and the element at *j* is greater than *key*, we need to find a new position for *key*.

7. *arr(j + 1) = arr(j)*: Shifting the element to make space for *key*.

8. *arr(j + 1) = key*: Placing the *key* in its correct position.

9. *Client Code*: Demonstrates how to use the *InsertionSort* object to sort an array.

With this approach, the array is successfully sorted in ascending order using the *Insertion Sort* algorithm in Scala.