Start learning free

LESSON 255 OF 338 · DIVIDE AND CONQUER

Merge Sort in Go: O(n log n) with a Shared Buffer

Practice O(n log n) Read the full explanation

In this video lesson we will study how the Merge Sort algorithm works, we will analyze its time and space complexities and then we will implement it:

Problem - Merge Sort:

Given an array of integers nums, sort it in ascending order using Merge Sort

Example 1:

Input: nums = [3, 1, 3, 2, 5, 4]
Output: [1, 2, 3, 3, 4, 5]

Note:

Your algorithm should run in O(n log n) time and use O(n) extra space.

STEP 1 OF 26
    Ctrl + Enter to check

    GO · DIVIDE AND CONQUER

    Merge Sort in Go, explained

    Problem overview

    The function sortArray(nums) sorts a slice of integers in ascending order using Merge Sort. It returns nothing: it rearranges the elements of nums itself. The statement asks for O(n log n) time and O(n) extra space.

    For nums = [3, 1, 3, 2, 5, 4] the slice becomes [1, 2, 3, 3, 4, 5]. Duplicates stay in the result.

    Approach: split, sort the halves, merge

    Merge Sort is divide and conquer in three moves:

    • Split the range in two halves.
    • Sort each half by calling the same function on it. A range of one element, or none, is already sorted, and that stops the recursion.
    • Merge the two sorted halves into one sorted range.

    The merge is the interesting part. Two sorted halves can be combined in a single pass: compare the front elements of both halves, copy the smaller one into a buffer, and advance in the half it came from. When one half runs out, copy the rest of the other, which is already in order.

    The ranges halve each time, so there are about log2(n) levels of splitting. The merges at one level touch every element once, which is O(n) work. Multiplied together, that is O(n log n), whatever the input order. That beats the O(n²) of simple sorts such as insertion sort. The cost is the buffer, which needs room for n elements.

    Take [1, 4, 6] and [2, 3, 9] next to each other. The comparisons pick 1, then 2, then 3, then 4, then 6. The left half is now empty, so the remaining 9 is copied. The result is [1, 2, 3, 4, 6, 9], after at most five comparisons.

    Step by step

    1. Declare the buffer mergeTemp as a package-level []int. Go has no classes to hold shared state, so a variable outside the functions lets every recursive call use the same buffer.
    2. Allocate it in sortArray with make, with length len(nums), since the last merge covers the whole slice.
    3. Start the recursion with mergeSort(nums, 0, len(nums)-1). Both bounds are inclusive.
    4. Declare mergeSort with the slice and the bounds left and right. It has no result, because it sorts in place.
    5. Base case. If left >= right, the range has at most one element, so return.
    6. Find the middle as left + (right-left)/2. The left half is left to middle and the right half is middle+1 to right.
    7. Sort the left half by calling mergeSort.
    8. Sort the right half by calling mergeSort.
    9. Merge. Call mergeSubarrays(nums, left, middle, right) to combine the sorted halves into nums[left..right].
    10. Declare mergeSubarrays with the indices left, middle and right.
    11. Set up three positions. i starts at left and walks the left half. j starts at middle + 1 and walks the right half. k starts at left and marks where the next element goes in mergeTemp.
    12. Merge while both halves have elements. Go has no while, so a for with only a condition does the job: i <= middle && j <= right.
    13. Pick the smaller front element. If nums[i] < nums[j], copy nums[i] and advance i. Otherwise copy nums[j] and advance j. Then advance k.
    14. Copy leftovers. One loop drains what remains of the left half and a second loop drains the right half. At most one of them does any work.
    15. Copy back. A last loop copies mergeTemp[left..right] into nums. It reuses i with =, since i already exists.

    The solution in Go

    var mergeTemp []int

func sortArray(nums []int) {
	mergeTemp = make([]int, len(nums))
	mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, left, right int) {
	if left >= right {
		return
	}
	middle := left + (right-left)/2
	mergeSort(nums, left, middle)
	mergeSort(nums, middle+1, right)
	mergeSubarrays(nums, left, middle, right)
}

func mergeSubarrays(nums []int, left, middle, right int) {
	i := left
	j := middle + 1
	k := left
	for i <= middle && j <= right {
		if nums[i] < nums[j] {
			mergeTemp[k] = nums[i]
			i++
		} else {
			mergeTemp[k] = nums[j]
			j++
		}
		k++
	}
	for i <= middle {
		mergeTemp[k] = nums[i]
		i++
		k++
	}
	for j <= right {
		mergeTemp[k] = nums[j]
		j++
		k++
	}
	for i = left; i <= right; i++ {
		nums[i] = mergeTemp[i]
	}
}

    Go details worth knowing:

    • The slice is sorted in place. A slice value shares its elements with the slice it was copied from, so writing nums[i] = mergeTemp[i] inside the helpers changes the caller's data. That is why none of the functions return anything.
    • Package-level state. mergeTemp is assigned in sortArray, not declared with a size, because a slice variable starts as nil with length 0. Each call to sortArray replaces it with a fresh buffer of the right length.
    • Stable or not. With <, equal elements are taken from the right half first. For plain integers the output is identical either way. Using <= would keep equal elements in their original order, which matters when sorting records by a key.
    • Reusing i. The final loop is for i = left; i <= right; i++. Writing i := left there would declare a second i that shadows the first, which also works, but this version reuses the existing one.
    • Overflow-safe middle. left + (right-left)/2 cannot overflow, while (left + right)/2 could for enormous indices.

    Complexity

    Time: O(n log n) in every case. There are about log2(n) levels, and the merges on one level do O(n) work in total, because each element is copied once into the buffer and once back.

    Space: O(n) for mergeTemp, plus O(log n) for the recursion stack. Allocating the buffer once, rather than inside every merge, avoids creating many small slices.

    Edge cases and common mistakes

    • Empty slice. right is -1, so left >= right holds and nothing happens.
    • One element. The base case returns at once.
    • Duplicates. [3, 1, 3, 2, 5, 4] keeps both 3s. The merge handles equal values like any other.
    • Negative numbers. Nothing depends on the sign. [-2, 7, 0, -2, 1] becomes [-2, -2, 0, 1, 7].
    • Copying back the wrong range. Only left to right was merged. Copying the whole buffer would overwrite elements outside the current range with stale values.
    • Starting k at 0. The buffer positions mirror the range, so k starts at left. Starting at 0 would break the copy-back loop.
    • Dropping the leftover loops. When one half finishes first, the remaining elements of the other must still be copied, or they are lost.
    • Overlapping halves. The halves are left..middle and middle+1..right. Letting middle belong to both would duplicate an element.

    Testing

    [3, 1, 3, 2, 5, 4] gives [1, 2, 3, 3, 4, 5]. An empty slice stays empty, [9] stays [9], and [-2, 7, 0, -2, 1] gives [-2, -2, 0, 1, 7].

    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free