Overview

Merge Sort is a divide-and-conquer algorithm that sorts an array by recursively dividing it into halves, sorting each half, and then merging the sorted halves. It has a time complexity of O(n log n) and is stable, making it a good choice for sorting large datasets.

Program Structure

The following Go program implements the Merge Sort algorithm. The program includes a main function that initializes an array, calls the merge sort function, and prints the sorted array.

Code Implementation

package main

import (
    "fmt"
)

// MergeSort sorts an array using the Merge Sort algorithm.
func MergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    
    mid := len(arr) / 2
    left := MergeSort(arr[:mid])
    right := MergeSort(arr[mid:])
    
    return merge(left, right)
}

// merge combines two sorted slices into one sorted slice.
func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0

    // Merge the two slices while there are elements in both
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    // Append any remaining elements
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)

    return result
}

func main() {
    arr := []int{38, 27, 43, 3, 9, 82, 10}
    fmt.Println("Original array:", arr)
    
    sortedArr := MergeSort(arr)
    fmt.Println("Sorted array:", sortedArr)
}

Function Documentation

• MergeSort(arr []int) []int: Takes an array of integers and returns a new sorted array using the Merge Sort algorithm.
• merge(left, right []int) []int: Merges two sorted arrays into a single sorted array.
• main(): The entry point of the program. It initializes an array, sorts it using MergeSort, and prints the original and sorted arrays.

How It Works

1. The MergeSort function checks if the array has one or no elements, returning it as it is already sorted.
2. It divides the array into two halves and recursively sorts each half.
3. The merge function then combines the two sorted halves by comparing the elements and appending the smaller one to the result.
4. This process continues until all elements are sorted and combined into a single sorted array.

Conclusion

This implementation of Merge Sort demonstrates the power of the divide-and-conquer strategy in algorithm design. With its efficient sorting capabilities, it remains a fundamental algorithm in computer science.