Debugging Grimoire

MergeSort Algorithm in Go

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func merge(sortedSlice1 []int, sortedSlice2 []int) []int {
	mergedSlice := make([]int, 0, len(sortedSlice1)+len(sortedSlice2))
	var index1, index2 int
	for index1 < len(sortedSlice1) && index2 < len(sortedSlice2) {
		if sortedSlice1[index1] < sortedSlice2[index2] {
			mergedSlice = append(mergedSlice, sortedSlice1[index1])
			index1++
		} else {
			mergedSlice = append(mergedSlice, sortedSlice2[index2])
			index2++
		}
	}
	mergedSlice = append(mergedSlice, sortedSlice1[index1:]...)
	mergedSlice = append(mergedSlice, sortedSlice2[index2:]...)
	return mergedSlice
}

func mergeSort(items []int) []int {
	if len(items) < 2 {
		return items
	}
	mid := len(items) / 2
	first := mergeSort(items[:mid])
	second := mergeSort(items[mid:])
	return merge(first, second)
}

func main() {
	const nElements = 10000
	unsortedSlice := make([]int, nElements)

	// generate numbers
	source := rand.NewSource(time.Now().UnixNano())
	rng := rand.New(source)

	for i := 0; i < nElements; i++ {
		unsortedSlice[i] = rng.Intn(10000)
	}

	sorted := mergeSort(unsortedSlice)

	fmt.Println(sorted[:100])
}

Key Concepts in Go

This example demonstrates:

1. Recursive Functions:
   • The mergeSort function showcases how recursion can simplify divide-and-conquer algorithms like MergeSort.
2. Slices in Go:
   • Efficiently splits and merges slices in a type-safe manner.
3. Custom Slice Operations:
   • Implements a merge function to combine two sorted slices.
4. Random Number Generation:
   • Uses math/rand to generate a large dataset for sorting.

Overview of MergeSort

MergeSort is a divide-and-conquer algorithm that:

1. Divides the input array into two halves recursively.
2. Conquers by sorting each half.
3. Merges the two sorted halves into a single sorted array.

It has a time complexity of (O(n \log n)), which makes it efficient for sorting large datasets.

Why a Go Implementation? While MergeSort is traditionally implemented in lower-level languages like C for performance, the Go implementation focuses on:

• Readability: The recursive approach and slice operations make the code easy to understand.
• Ease of Use: Go's built-in slice handling eliminates the need for manual memory management.

Real-World Applications

1. Database Systems:
   • Efficiently sorts large datasets stored in external memory (e.g., disk or SSD).
2. Parallel Computing:
   • Its divide-and-conquer nature makes it suitable for parallelization.
3. Merging Sorted Data:
   • Combines multiple sorted data streams in distributed systems.
4. Sorting Algorithms in Libraries:
   • Often used as a fallback for sorting libraries when data size is too large for in-place algorithms like QuickSort.

Code Explanation

The code can be divided into logical sections:

1. Merge Function:

   func merge(sortedSlice1 []int, sortedSlice2 []int) []int {
       mergedSlice := make([]int, 0, len(sortedSlice1)+len(sortedSlice2))
       var index1, index2 int
       for index1 < len(sortedSlice1) && index2 < len(sortedSlice2) {
           if sortedSlice1[index1] < sortedSlice2[index2] {
               mergedSlice = append(mergedSlice, sortedSlice1[index1])
               index1++
           } else {
               mergedSlice = append(mergedSlice, sortedSlice2[index2])
               index2++
           }
       }
       mergedSlice = append(mergedSlice, sortedSlice1[index1:]...)
       mergedSlice = append(mergedSlice, sortedSlice2[index2:]...)
       return mergedSlice
   }
   

   • Combines two sorted slices (sortedSlice1 and sortedSlice2) into a single sorted slice.
   • Maintains stability, meaning the order of equal elements is preserved.

2. MergeSort Function:

   func mergeSort(items []int) []int {
       if len(items) < 2 {
           return items
       }
       mid := len(items) / 2
       first := mergeSort(items[:mid])
       second := mergeSort(items[mid:])
       return merge(first, second)
   }
   

   • Recursively divides the input slice into halves until each slice contains one or zero elements.
   • Merges the sorted halves back together using the merge function.

3. Main Function:

   func main() {
       const nElements = 10000
       unsortedSlice := make([]int, nElements)
   
       source := rand.NewSource(time.Now().UnixNano())
       rng := rand.New(source)
   
       for i := 0; i < nElements; i++ {
           unsortedSlice[i] = rng.Intn(10000)
       }
   
       sorted := mergeSort(unsortedSlice)
   
       fmt.Println(sorted[:100])
   }
   

   • Generates a slice of 10,000 random integers.
   • Sorts the slice using the mergeSort function.
   • Prints the first 100 sorted elements for verification.

Example output:

[0 5 12 16 21 ... 9876 9999]

Extensions

1. Parallelization:
   • Use goroutines to parallelize the sorting of the two halves.
2. Custom Comparators:
   • Modify the merge function to support custom sorting criteria (e.g., descending order or by specific object attributes).
3. Benchmarking:
   • Compare the performance of this implementation with Go's built-in sort package.
4. Visualization:
   • Create a graphical representation of how MergeSort works step-by-step.