Merge Sort Algorithm in Scala

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.