# 1. Introduction

Merge Sort is a divide-and-conquer algorithm that recursively divides a list into two halves until each sublist consists of a single element. Then, it merges these sublists to produce new sorted sublists until there's only one sublist remaining.

# 2. Implementation Steps

1. Divide the unsorted list into n sublists, each containing one element.

2. Repeatedly merge sublists to produce new sorted sublists until there's only one sublist remaining.

# 3. Implementation in Scala

``````object MergeSort {
def mergeSort(lst: List[Int]): List[Int] = {
val mid = lst.length / 2
if (mid == 0) lst
else {
val (left, right) = lst.splitAt(mid)
merge(mergeSort(left), mergeSort(right))
}
}
def merge(left: List[Int], right: List[Int]): List[Int] =
(left, right) match {
case (Nil, right) => right
case (left, Nil) => left
case (l :: leftTail, r :: rightTail) =>
if (l < r) l :: merge(leftTail, right)
else r :: merge(left, rightTail)
}
}
``````

### Client Code:

``````val numbers = List(38, 27, 43, 3, 9, 82, 10)
println("Original List: " + numbers)
val sortedList = MergeSort.mergeSort(numbers)
println("Sorted List: " + sortedList)
``````

### Output:

```Original List: List(38, 27, 43, 3, 9, 82, 10)
Sorted List: List(3, 9, 10, 27, 38, 43, 82)
```

### Explanation:

1. object MergeSort: This is the singleton object for the Merge Sort algorithm in Scala.

2. mergeSort(lst: List[Int]): A recursive function that sorts a list by dividing it into two halves, sorting each half, and then merging them together.

3. val mid = lst.length / 2: Find the midpoint of the list.

4. splitAt(mid): Splits the list into two halves.

5. merge(left, right): This is a helper function to merge two sorted lists.

6. (left, right) match: Pattern matching is used to determine the merging strategy based on the elements of the left and right lists.

7. case (Nil, right) => right: If the left list is empty, the merged list is the right list.

8. case (left, Nil) => left: If the right list is empty, the merged list is the left list.

9. l :: merge(leftTail, right) and r :: merge(left, rightTail): Merging elements in order while preserving their order.

10. Client Code: Demonstrates how to use the MergeSort object to sort a list of integers.

The Merge Sort algorithm uses a recursive approach to divide the original list into smaller parts and then merge these parts in a sorted manner, resulting in a sorted list.