Merge Sort in Go

Hello, again, dedicated learner! You've already mastered the essentials of Quick Sort, and today, we're venturing into the realm of Merge Sort. Like sorting a shuffled deck of cards, Merge Sort excels in efficiently managing large datasets. Together, we'll explore, implement, and analyze its performance in Go. Ready to advance further on this journey? Let's dive in!

Merge Sort is an efficient and popular sorting technique in computer science, deploying a divide-and-conquer approach similar to Quick Sort. The main steps involve:

1. Splitting the array into halves.
2. Sorting each half individually.
3. Merging the sorted halves back into a complete array.

We will now cover all of the code required to implement Merge Sort, starting with a merge function:

package main

import "fmt"

func merge(arr, left, right []int) {
    i, j := 0, 0 // Initialize pointers for left and right slices
    for k := 0; k < len(arr); k++ {
        // Compare elements from left and right and merge sorted elements into arr
        if j >= len(right) || (i < len(left) && left[i] <= right[j]) {
            arr[k] = left[i]
            i++
        } else {
            arr[k] = right[j]
            j++
        }
    }
}

The merge() function combines two sorted halves, the left and right arrays, back into a resulting array. Using pointers to traverse the left and right arrays, as well as the resulting array, it compares elements from the left and right arrays. The smaller element is placed into the resulting array. If the right array is exhausted or the current element from the left array is smaller or equal, the element from the left array is placed into the resulting array, and the pointer for the left array is incremented. Otherwise, the element from the right array is placed into the resulting array, and the pointer for the right array is incremented. This process continues until all elements are merged into the resulting array.

Next, let's look at how the mergeSort function uses merge to sort an array:

func mergeSort(arr []int) {
    if len(arr) < 2 { // Base case: arrays with less than 2 elements are already sorted
        return
    }

    mid := len(arr) / 2
    // Split the array into left and right halves
    left, right := append([]int{}, arr[:mid]...), append([]int{}, arr[mid:]...)

    mergeSort(left)  // Recursively sort the left half
    mergeSort(right) // Recursively sort the right half
    merge(arr, left, right) // Merge the sorted halves
}

The mergeSort() function is the main function responsible for splitting the array into halves, sorting each half, and then merging them. It first checks if the length of arr is less than two, returning immediately as such arrays are already sorted (base case). It calculates the midpoint, mid, to split arr into two halves: left and right. These are created as new slices using append() to avoid altering the original array. Recursively, mergeSort() is applied to both left and right until the base case is met. After sorting, the halves are merged using the merge() function.