---
title: "Merge Sort and Divide and Conquer"
description: "Sorting by splitting the data in half, sorting each half the same way, then merging two sorted halves in one pass. The splitting gives log n levels and each level costs n, which is where O(n log n) co"
canonical: https://lightmysky.com/learn/computing/merge-sort-and-divide-and-conquer-mt_OAutL4c7_l
source: https://lightmysky.com/learn/computing/merge-sort-and-divide-and-conquer-mt_OAutL4c7_l.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Merge Sort and Divide and Conquer

Sorting by splitting the data in half, sorting each half the same way, then merging two sorted halves in one pass. The splitting gives log n levels and each level costs n, which is where O(n log n) comes from.

Subject: Computing · Area: Algorithms & Data Structures · Ages 17 to 18
Page: https://lightmysky.com/learn/computing/merge-sort-and-divide-and-conquer-mt_OAutL4c7_l

## Ready when they can

- Merge two sorted lists into one and count the comparisons the merge needs
- Draw the split-and-merge tree for eight values and count its levels
- Explain why O(n log n) beats O(n squared) badly once the input is large

## Lesson: Sorting by splitting in half

Merge sort is divide and conquer: you split the data in half, sort each half the same way, then merge the halves. A list of one item or none is already sorted, so that is your base case and all real work sits in the merges.

**Example.** You merge with two fingers, always copying the smaller front value into the result. Merging 1 4 6 with 2 3 5 takes 5 comparisons and gives 1 2 3 4 5 6. Splitting 8 values down to ones takes 3 levels, since 8 halves to 4, then 2, then 1.

Each level merges all n items with linear work, and there are about log n levels, so the total is order n log n. When n doubles, this work a bit more than doubles, while quadratic work quadruples. That gentle growth is why it beats order n squared badly on large inputs.

**Tip.** You trace it on paper by splitting to ones first, then merging pairs while counting comparisons aloud. Sketch the tree for eight values and check you see three split levels before you trust the running time argument.

**Recap.** Split to ones, merge in order, and log n levels of linear work give n log n.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Quadratic Sorts: Bubble and Insertion](https://lightmysky.com/learn/computing/quadratic-sorts-bubble-and-insertion-mt_cBUIBa15jQ)
- [Recursion and the Call Stack](https://lightmysky.com/learn/computing/recursion-and-the-call-stack-mt_VGjfeF3F2e)

## Opens up

- [Trees and Binary Search Trees](https://lightmysky.com/learn/computing/trees-and-binary-search-trees-mt_7PGHiAY54b)
- [Recurrence Relations and the Master Theorem](https://lightmysky.com/learn/computing/recurrence-relations-and-the-master-theorem-mt_aOvLPV7rR8)
- [Divide and Conquer as a Design Method](https://lightmysky.com/learn/computing/divide-and-conquer-as-a-design-method-mt_YITRNb-HTE)