Merge Sort

DSA · Sorting Algorithms

Theory

Merge sort is a divide-and-conquer algorithm: it splits the list in half, recursively sorts each half, then merges the two sorted halves by repeatedly taking the smaller front element. The recursion depth is log n and each level does O(n) merging work, so it always runs in O(n log n). It needs O(n) extra memory for merging and is stable.

Why we use it

It guarantees O(n log n) regardless of input order and is stable, which makes it reliable for large data and for sorting linked lists and external files.

When to use it

Use it when you need guaranteed performance, stability, sorting linked lists, or sorting data too large for memory (external merge sort).

How it works

  1. mergeSort(arr)
  2. Length <= 1? Yes: Return arr (already sorted). No: Split into left and right halves.
  3. Sort left half recursively
  4. Sort right half recursively
  5. Merge: repeatedly take the smaller front element
  6. Return merged sorted array

Syntax

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

Time: O(n log n) always   Space: O(n)   Stable

Example

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    merged += left[i:] + right[j:]
    return merged

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic