Merge Sort with Kotlin

Hello, aspiring programmers! Today's topic is "Merge Sort." Merge Sort is a sorting technique akin to arranging a deck of shuffled cards in order. However, for data at the Internet scale, Merge Sort outperforms your regular techniques. Today, we'll explore Merge Sort, code it in Kotlin, and analyze its speed. Ready? Let's get started!

In computer science, Merge Sort is a popular method to sort elements. Merge Sort uses the same 'divide-and-conquer' strategy for sorting as the familiar Quick Sort algorithm. Imagine you have one long music playlist mixed up with songs. You want to sort these songs from A to Z. That's what Merge Sort does to an array.

In the three steps of Merge Sort:

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

We will start by building code for merging two sorted parts. The merge process involves making two halves play sort and seek. It compares elements from two halves and merges them so that the resulting list is sorted as well.

Let's code a merge() function in Kotlin that will do just that. Note that the final variant of the merge sort function will perform every operation "in place," meaning there will not be two actual arrays; we will operate on parts of one array. With this in mind, let's implement the merge function to take just one array and treat its parts like separate arrays.

fun merge(arr: IntArray, left: Int, mid: Int, right: Int) {
    val n1 = mid - left + 1 // Find number of elements in the left array
    val leftArray = IntArray(n1) // Define left array

    val n2 = right - mid // Find number of elements in the right array
    val rightArray = IntArray(n2) // Define right array

    // Let's fill in these arrays
    for (i in 0 until n1)
        leftArray[i] = arr[left + i]
    for (j in 0 until n2)
        rightArray[j] = arr[mid + 1 + j]
}

So far, we've divided our original list into two halves, leftArray and rightArray.

Now, we'll sort and merge these halves:

    var i = 0
    var j = 0
    var k = left
    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i]
            i++
        } else {
            arr[k] = rightArray[j]
            j++
        }
        k++
    }
}

Though seemingly tricky, the code is straightforward:
We place two pointers, i and j, at the beginning of the leftArray and rightArray.
We choose the smaller element, put it in the final array arr, and move the corresponding pointer further.
We keep doing this until one of the pointers reaches the end of its array.