Merge Sort Trace

Idea of Merge Sort:

1. Keep dividing the elements until only 1 element is left.
2. Then merge the sorted elements.
3. In merging the sorted elements, we copy the two halves and finally merge to the initial array.
4. TC : O(nlogn) & SC : O(n)

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscan(reader, &n)

	slice := make([]int, n)
	for i := range n {
		fmt.Fscan(reader, &slice[i])
	}

	mergeSort(slice, 0, n-1, writer)
}

func mergeSortedArrays(slice []int, l, mid, r int) {
	//merge logic begins here.
	//Idea.
	left := make([]int, mid-l+1)
	right := make([]int, r-mid)

	idx := 0
	for i := l; i <= mid; i++ {
		left[idx] = slice[i]
		idx++
	}

	idx = 0
	for i := mid + 1; i <= r; i++ {
		right[idx] = slice[i]
		idx++
	}

	i, j, k := 0, 0, l
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			slice[k] = left[i]
			i++
		} else {
			slice[k] = right[j]
			j++
		}
		k++
	}

	for i < len(left) {
		slice[k] = left[i]
		i++
		k++
	}

	for j < len(right) {
		slice[k] = right[j]
		j++
		k++
	}

}

func mergeSort(slice []int, l, r int, w io.Writer) {
	//base case.
	if l >= r {
		return
	}

	mid := (l + r) / 2

	fmt.Fprintf(w, "Divide: [%d %d]\n", l, r)

	mergeSort(slice, l, mid, w)
	mergeSort(slice, mid+1, r, w)

	mergeSortedArrays(slice, l, mid, r)
	fmt.Fprintf(w, "Merge: [%d %d] -> ", l, r)
	for i := l; i <= r; i++ {
		fmt.Fprint(w, slice[i], " ")
	}
	fmt.Fprintln(w)
}