Merge Sort – Go Program

Go – Merge Sort

In this tutorial, we will learn how to implement the Merge Sort algorithm using the Go programming language (Golang).

Merge Sort is a divide-and-conquer sorting algorithm that splits the list into smaller sublists, sorts them recursively, and then merges them back together in sorted order. It is an efficient sorting algorithm with a time complexity of \( O(n \log n) \).

We will provide a detailed explanation and an example program to implement Merge Sort.

---

Logic of Merge Sort

The Merge Sort algorithm involves the following steps:

1. Divide the List: Recursively divide the list into two halves until each sublist contains a single element.
2. Sort the Sublists: Recursively sort the sublists.
3. Merge Sublists: Merge the sorted sublists back together to form a sorted list.
4. Repeat: Continue merging until the entire list is sorted.

Merge Sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements.

---

Go Program for Merge Sort

Program – merge_sort.go

package main

import "fmt"

// Function to merge two sorted slices
func merge(left, right []int) []int {
    merged := []int{}
    i, j := 0, 0

    // Merge the two slices into a sorted slice
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            merged = append(merged, left[i])
            i++
        } else {
            merged = append(merged, right[j])
            j++
        }
    }

    // Append any remaining elements from the left slice
    for i < len(left) {
        merged = append(merged, left[i])
        i++
    }

    // Append any remaining elements from the right slice
    for j < len(right) {
        merged = append(merged, right[j])
        j++
    }

    return merged
}

// Recursive function to implement Merge Sort
func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    // Find the middle index
    mid := len(arr) / 2

    // Divide the array into left and right halves
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])

    // Merge the sorted halves
    return merge(left, right)
}

func main() {
    // Input array
    arr := []int{38, 27, 43, 3, 9, 82, 10}

    // Display the original array
    fmt.Println("Original array:", arr)

    // Sort the array using Merge Sort
    sortedArr := mergeSort(arr)

    // Display the sorted array
    fmt.Println("Sorted array:", sortedArr)
}

Explanation of Program

1. Function Definition: The mergeSort function recursively divides the list into smaller sublists, sorts them, and merges them back together.
2. Merge Function: The merge function takes two sorted slices, compares their elements, and combines them into a single sorted slice.
3. Base Case: If the length of the list is less than or equal to 1, the list is already sorted, and it is returned as-is.
4. Recursive Case: The list is divided into two halves, which are sorted recursively using mergeSort. The sorted halves are then merged using the merge function.
5. Display Results: The original and sorted arrays are printed using fmt.Println.

Output

This program demonstrates the Merge Sort algorithm, which recursively divides and merges elements to achieve a sorted list.