Merge Sort
Merge Sort is an efficient and stable sorting algorithm based on the divide-and-conquer paradigm, widely used in scenarios requiring stable sorting. It recursively divides an array into smaller subarrays, sorts them individually, and then merges them into a sorted array. This article explains the principle and steps of Merge Sort in detail, providing code examples in C and Go to help beginners get started quickly.
Principle
The core idea of Merge Sort is:
- Divide: Recursively divide the array into two subarrays until the subarray length is 1 (a single element is considered sorted).
- Conquer: Merge two sorted subarrays to create a new sorted array.
- Repeat the above steps until the entire array is sorted.
Its time complexity is O(n log n), where n is the length of the array, and it remains consistent regardless of the input data. Merge Sort requires additional space to store temporary arrays, so its space complexity is O(n). Its stability makes it suitable for scenarios where the relative order of equal elements needs to be preserved.
Steps
Assuming we want to sort an integer array in ascending order, here are the detailed steps for Merge Sort:
- Partition: Divide the array into two roughly equal subarrays and recursively sort each subarray.
- Termination Condition: When the subarray length is 1, stop partitioning (a single element is already sorted).
- Merge: Merge two sorted subarrays into a single sorted array by comparing the elements of the two subarrays and sequentially selecting the smaller element to place in the resulting array.
- Repeat: Recursively perform the above steps for all subarrays until the entire array is sorted.
Implementation
- C
- Go
Here is the C implementation of Merge Sort, with detailed comments to aid understanding.
#include <stdio.h>
#include <stdlib.h>
// Merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1; // Length of the left subarray
int n2 = right - mid; // Length of the right subarray
// Create temporary arrays
int *L = (int *)malloc(n1 * sizeof(int));
int *R = (int *)malloc(n2 * sizeof(int));
// Copy data to temporary arrays
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge the temporary arrays back into the original array
i = 0; // Index of the left subarray
j = 0; // Index of the right subarray
k = left; // Index of the merged array
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of the left subarray
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of the right subarray
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
// Free the temporary arrays
free(L);
free(R);
}
// Merge Sort function
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // Calculate the middle index
// Recursively sort the left half
mergeSort(arr, left, mid);
// Recursively sort the right half
mergeSort(arr, mid + 1, right);
// Merge the sorted subarrays
merge(arr, left, mid, right);
}
}
// Helper function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Main function to test merge sort
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
$ gcc -o bin/merge-sort main.c
$ bin/merge-sort
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90
$
Here is the Go implementation of Merge Sort, with detailed comments to aid understanding.
package main
import "fmt"
// merge merges two sorted subarrays
func merge(arr []int, left, mid, right int) {
n1 := mid - left + 1 // Length of the left subarray
n2 := right - mid // Length of the right subarray
// Create temporary slices
L := make([]int, n1)
R := make([]int, n2)
// Copy data to temporary slices
for i := 0; i < n1; i++ {
L[i] = arr[left+i]
}
for j := 0; j < n2; j++ {
R[j] = arr[mid+1+j]
}
// Merge the temporary slices back into the original array
i := 0 // Index of the left subarray
j := 0 // Index of the right subarray
k := left // Index of the merged array
for i < n1 && j < n2 {
if L[i] <= R[j] {
arr[k] = L[i]
i++
} else {
arr[k] = R[j]
j++
}
k++
}
// Copy the remaining elements of the left subarray
for i < n1 {
arr[k] = L[i]
i++
k++
}
// Copy the remaining elements of the right subarray
for j < n2 {
arr[k] = R[j]
j++
k++
}
}
// mergeSort implements the merge sort algorithm
func mergeSort(arr []int, left, right int) {
if left < right {
mid := left + (right-left)/2 // Calculate the middle index
// Recursively sort the left half
mergeSort(arr, left, mid);
// Recursively sort the right half
mergeSort(arr, mid+1, right);
// Merge the sorted subarrays
merge(arr, left, mid, right);
}
}
// printArray prints the elements of an array
func printArray(arr []int) {
for _, val := range arr {
fmt.Printf("%d ", val)
}
fmt.Println()
}
func main() {
// Example array
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Print("Original array: ");
printArray(arr)
mergeSort(arr, 0, len(arr)-1)
fmt.Print("Sorted array: ");
printArray(arr)
}
$ gsk build -v
create merge-sort/bin/merge-sort-linux-amd64
$ ./bin/merge-sort-linux-amd64
Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90
Summary
The core of Merge Sort is to recursively divide the array into smaller chunks using the divide-and-conquer approach, sort them individually, and then merge them into a sorted array, ensuring stable sorting characteristics.
Copyright Notice: Freely reproduced, non-commercial, no derivatives, attribution, and keep the source.
Author: afxcn
Source: https://gostartkit.com/docs/algo/merge-sort
Date Published: June 28, 2025