Lesson menuPython TutorialHideShow

Python Tutorial

Merge Sort

A stable divide-and-conquer sort with a guaranteed O(n log n) — split, sort halves, then merge.

← Radix SortMySQL Get Started →

Divide, Conquer, Merge

Merge sort splits the array in half, recursively sorts each half, then merges the two sorted halves into one. Because merging two sorted lists is linear and the recursion is log-deep, the total is a guaranteed O(n log n) — in the best, average, and worst case.

Implementation

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])     # sort left half
    right = merge_sort(arr[mid:])     # sort right half
    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]:       # <= keeps it STABLE
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])           # append any remainder
    result.extend(right[j:])
    return result

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

The Merge Step Visualized

Merging [3, 27, 43] and [9, 10, 82]: compare fronts, take the smaller each time.

CompareTakeResult so far
3 vs 93[3]
27 vs 99[3, 9]
27 vs 1010[3, 9, 10]
27 vs 8227[3, 9, 10, 27]

Complexity

CaseTime
Best / Average / WorstO(n log n) — always
SpaceO(n) extra for merging
Stable?Yes

Its predictable performance and stability make merge sort the algorithm of choice when worst-case guarantees matter or when sorting linked lists and huge external files.

Merge Sort vs Quick Sort

  • Merge sort: guaranteed O(n log n), stable, but O(n) extra memory.
  • Quick sort: in-place and usually faster, but O(n²) worst case and not stable.
  • External sorting of data too big for RAM uses merge sort's merge step across disk chunks.

Python's built-in Timsort is a hybrid of merge sort and insertion sort — it is stable and O(n log n), and exploits already-sorted runs for near-O(n) performance on real data.

Best Practices

  • Choose merge sort when you need stability and a hard O(n log n) guarantee.
  • Use <= in the merge to preserve stability.
  • For linked lists, merge sort avoids random access and is the natural choice.
  • In production, reach for sorted() — you get Timsort's merge-sort benefits for free.

Try It Yourself

Exercise 1: Merge two sorted lists [1, 4, 7] and [2, 3, 8] by hand — what is the result?

Show solution

[1, 2, 3, 4, 7, 8] — repeatedly take the smaller front element.

Exercise 2: Name merge sort's one downside versus quicksort.

Show solution

It needs O(n) extra memory for merging, whereas quicksort sorts in place.

📘 Real-World Deep Dive

Knowing <strong>DSA Merge Sort (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.

Real-Life Scenario

An end-to-end usage of DSA Merge Sort that you'd actually see in a data pipeline or analytics notebook.

Real-Life Example

def msort(xs):
    if len(xs) <= 1: return xs
    mid = len(xs)//2
    a = msort(xs[:mid]); b = msort(xs[mid:])
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]: out.append(a[i]); i += 1
        else:             out.append(b[j]); j += 1
    out.extend(a[i:]); out.extend(b[j:])
    return out

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

Expected Output

(see source)

Common mistakes

  • Off-by-one errors in binary-search: the standard idiom is while lo <= hi with mid = (lo + hi) // 2.
  • Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
  • Comparison algorithms (sorted(iterable)) are stable by default in Python — surprising for Java/C++ users.
  • Treating DSA Merge Sort as a black box without reading the docs — the API has subtle defaults that bite when you scale.

🚀 Performance & Best Practices

  • Use bisect.bisect_left / bisect_right instead of writing your own binary search.
  • Convert a sorted search into a tuple-access pattern with numpy.searchsorted for huge arrays.
  • Use heapq for priority queues instead of maintaining a sorted list manually.
  • When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.

🧪 Try It Yourself

  1. Reproduce the snippet on a representative slice of your own data.
  2. Profile the snippet with cProfile or timeit and find the single biggest improvement.
  3. Generalise the snippet into a small, reusable function you can drop into future projects.

FAQ: Merge Sort

Common questions about this page.

What is Merge Sort?

Merge Sort is a DSA lesson that explains merge sort in Python. A stable divide-and-conquer sort with a guaranteed O(n log n) — split, sort halves, then merge. Copy the samples and run them in the Python editor. It is written for beginners who want a clear definition and working examples.

Should I run merge sort examples locally for better learning?

Yes. Use the browser editor on StudyGrid for a quick check, then Download the example and run it on your computer. Local runs show real errors and the real toolchain, which is one of the fastest ways to learn merge sort in this DSA Python lesson (Merge Sort).

How do I use merge sort in Python?

To use merge sort in Python, follow the examples on this StudyGrid page. Copy a snippet, run it in the browser, then Download and run it locally for better learning. Change the values and compare the output.

What is the syntax of merge sort?

This Merge Sort tutorial shows merge sort syntax with short Python examples. Use the code blocks in this lesson for the exact statements, then try them in your editor.

Merge Sort example for beginners

Yes. This page includes a beginner merge sort example you can copy and run. It is designed for searches such as "merge sort for beginners", "merge sort example", and "how to use merge sort".

What are common mistakes with merge sort?

Common merge sort mistakes include wrong syntax, mixing types, and skipping practice. Work through this DSA chapter in order, run every example, and check the output before moving on.

Why should I learn merge sort?

Merge Sort is used in real Python work. Learning merge sort helps you write clearer programs and continue the DSA tutorial on StudyGrid.

Is Merge Sort free to learn online?

Yes. You can learn merge sort free on StudyGrid (studygrid.in). This chapter is part of the DSA path and includes examples, syntax, and next-step links.