Merge Sort - Algorithm, Visualization, Examples

Problem Statement❯

Given an array of integers, your task is to sort the array in ascending order using the Merge Sort algorithm.

Merge Sort is a divide and conquer algorithm. It divides the array into halves, recursively sorts them, and then merges the sorted halves into one final sorted array.

This algorithm is stable and guarantees a worst-case time complexity of O(n log n).

Examples❯

Input Array	Sorted Output	Description
[4, 2, 7, 1, 9, 3]	[1, 2, 3, 4, 7, 9]	Unsorted array is recursively divided and merged into a sorted version.
[1, 2, 3, 4]	[1, 2, 3, 4]	Already sorted input still goes through divide and merge steps.
[4, 4, 4, 4]	[4, 4, 4, 4]	All elements are equal. Merge Sort maintains the original order (stable).
[10]	[10]	Single-element array is already sorted. No merging needed.
[]	[]	Empty array returns an empty result. No action is performed.
[5, -2, 0, 3, -7]	[-7, -2, 0, 3, 5]	Handles negative numbers and zero correctly in sorting.

Visualization Player

Solution❯

Merge Sort is a popular sorting technique that follows the Divide and Conquer strategy. Instead of solving the problem directly, it breaks it into smaller subproblems, solves those, and then combines the results. This makes it both elegant and efficient for large datasets.

How Merge Sort Works

At a high level, here's what Merge Sort does:

It keeps dividing the array into two halves until each part has just one element.
Then, it merges those small arrays back together in sorted order.

Understanding with Different Cases

Case 1: Normal array

Take the array [4, 2, 7, 1]. It will first be divided into [4, 2] and [7, 1], then further down to [4], [2], [7], and [1]. These are then merged into [2, 4] and [1, 7], and finally into [1, 2, 4, 7].

Case 2: Already sorted array

Even if the array is sorted (e.g., [1, 2, 3, 4]), Merge Sort will still divide and merge it. Though the end result is the same, the algorithm will still run all its steps.

Case 3: All elements are equal

For input like [5, 5, 5, 5], the output is also [5, 5, 5, 5]. Merge Sort maintains the original order, which is a property known as stability.

Case 4: Single-element array

In this case (e.g., [10]), the array is already sorted. The algorithm detects this and does not perform any merging.

Case 5: Empty array

If the input is an empty array [], there's nothing to sort, and the output is also an empty array.

Case 6: Array with negative numbers

Merge Sort works perfectly with negative values too. For example, [5, -2, 0] becomes [-2, 0, 5] after sorting.

Why Merge Sort Is Useful

Merge Sort guarantees a worst-case performance of O(n log n), making it ideal for large datasets. It is also a stable sort, meaning equal elements retain their original order — which can be important in some applications (like sorting objects based on multiple fields).

Algorithm Steps❯

Divide the unsorted array into n subarrays, each containing one element.
Repeatedly merge subarrays to produce new sorted subarrays until there is only one subarray remaining.
The final subarray is the sorted array.

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    sorted_arr = merge_sort(arr)
    print("Sorted array is:", sorted_arr)

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n log n)	Merge Sort always divides the array into halves and merges them, regardless of the input order. Even if the array is already sorted, it still performs the same number of comparisons and merges.
Average Case	O(n log n)	In the average case, the array is recursively divided into halves (log n levels), and merging at each level takes O(n) time. Therefore, total time complexity is O(n log n).
Worst Case	O(n log n)	Even in the worst case, Merge Sort does not change its behavior — it still performs log n levels of merging with O(n) work at each level, leading to O(n log n) time.

Space Complexity❯

O(n)

Explanation: Merge Sort requires additional space to store temporary subarrays during the merge process. This auxiliary space grows linearly with the input size.

⬅ Previous TopicInsertion Sort

Next Topic ⮕Quick Sort