Merge Sort in Scala: A Comprehensive Guide

Welcome, aspiring programmer! Today, we're diving into Merge Sort. Merge Sort is a powerful sorting technique akin to organizing a shuffled deck of cards, but it excels when it comes to sorting data on an internet scale. In this lesson, we'll explore Merge Sort, code it in Scala, and analyze its performance. Ready? Let's get started!

In computer science, Merge Sort is a popular method for sorting elements. Merge Sort employs a "divide-and-conquer" strategy, much like the well-known Quick Sort algorithm. It follows these three main steps:

1. Split the array into halves.
2. Sort each half separately.
3. Merge the sorted halves back together.

Let's start by writing code to handle merging two sorted parts of a collection. The merging process allows the two halves to interact by comparing elements and combining them into a sorted result.

Let's implement a merge function in Scala that achieves this. To merge two sorted subarrays efficiently, we'll use auxiliary arrays to temporarily hold the data while we combine them back into the original array:

def merge(arr: Array[Int], left: Int, mid: Int, right: Int): Unit = {
  // Calculate the number of elements in the left and right arrays
  val n1 = mid - left + 1
  val n2 = right - mid
  
  // Create temporary arrays for left and right subarrays
  val Left = Array.ofDim[Int](n1)
  val Right = Array.ofDim[Int](n2)

  // Fill the left and right arrays
  for (i <- 0 until n1)
    Left(i) = arr(left + i)
  for (j <- 0 until n2)
    Right(j) = arr(mid + 1 + j)
}

We've now copied sections of the original array into two temporary arrays, Left and Right. This auxiliary space is necessary for the merging process.

Now, let's sort and merge these halves:

var i = 0
var j = 0
var k = left

while (i < n1 && j < n2) {
  if (Left(i) <= Right(j)) {
    arr(k) = Left(i)
    i += 1
  } else {
    arr(k) = Right(j)
    j += 1
  }
  k += 1
}

The logic is straightforward: We use two pointers, i and j, to track positions in the Left and Right arrays. By comparing elements, we choose the smaller one and place it in the array arr, advancing the respective pointer. We continue this until one pointer traverses its entire array.