Give

Merge sort

Divide and conquer: split, sort the halves and merge them back.

Back to Coding · Searching and sorting

Planned. This module is part of the plan and is not written yet.

COCO-ALG-SRT-0404Level11–13

Why it matters

Sorting a tall stack of exam scripts is quicker if two people each sort half, then merge their piles by always taking the smaller top script. That is merge sort.

Draft outline · in review
For
Level 11–13 · SSS 2 to A level / JUPEB / foundation year
Inside
5 lessons and a test · about 90 minutes
Topic
Searching and sorting · extension, 3 of 4
Plate CO-ALG-SRT-04: planned.

Inside the module.

5 lessons in order, about 90 minutes in all, then a short test. Learners go at their own pace; the minutes are a guide, not a timetable.

Draft outline · in review

  1. Lesson 1: Divide and conquer

    Split a problem in half, solve each half and combine the answers.

    Explain15 min, from minute 0

  2. Lesson 2: Merging two sorted lists

    Combine two sorted piles by always taking the smaller front item.

    Worked example15 min, from minute 15

  3. Lesson 3: Merge sort, traced

    Split [8, 3, 5, 1, 9, 2] down to single items and merge back up.

    Worked example20 min, from minute 30

  4. Lesson 4: Merge sort in Python

    Write merge sort recursively and test it.

    Practice30 min, from minute 50

  5. Lesson 5: Why it is fast

    About log₂ n levels of splitting, with n steps of merging at each: O(n log n).

    Review10 min, from minute 80

  6. End-of-module test

    Explain divide and conquer and implement merge sort recursively in Python.

    Mastered at 85% or more. Retake it until you pass; nothing is lost, and each try gives feedback.

    Already know it? A Challenge Test (planned) clears the whole module: 90% overall, no objective below 75%.

    Last stageafter about 90 min

Practicalities

Draft outline · in review

  • Built to run offline

    Planned to run on the Lantern's own computer, with no internet needed.

  • Languages

    Planned first in English; every module aims to reach all of the Lantern's languages.

Try a question.

One question from the module, as a learner would meet it. Have a go, then open the worked solution a step at a time.

Draft outline · in review

Merge the sorted lists [2, 7, 9] and [3, 4, 10] the way merge sort does. What is the result?

Work it out on paper first, then show the answer and mark it yourself.

Particulars

Where it sits

Coding · Algorithms & data structures · Searching and sorting

What a learner can do after it

  1. Explain divide and conquer.
  2. Implement merge sort recursively.

Needs first

Unlocks

Level

Level 11–13 · SSS 2 to A level / JUPEB / foundation year

Show levels in

Level mappings are approximate. A qualified teacher or lecturer in each country must check them before they appear in the app. Levels 13–18 describe the content, not the learner: “Level 15” means material usually taught in a second-year university course, whoever chooses to learn it.

Difficulty for its level

3 of 4 · Extension

Time

About 90 minutes

Alignments

  • Aligned to GCSEpartial · in reviewGCSE Computer Science: sorting algorithms (descriptive ref)
  • Aligned to APpartial · in reviewAP Computer Science A: sorting (descriptive ref)

Alignment in review until a qualified teacher or lecturer checks it. No exam body, university or vendor endorses us; learners still sit the real exam. University-level modules give knowledge, not university credit.

Challenge Test

Planned: a Challenge Test to prove you know it and skip it. Pass at 90% overall, with no objective below 75%.

University courses it previews

Computer Science, Software Engineering

On these pathways

The route here.

Everything this module builds on, drawn as a route from its foundations. Solid lanes must be mastered first, or cleared by a Challenge Test; dashed lanes are suggestions that never lock anything.

From Level 1, Instructions in order to Level 7, Substituting into formulae
  1. CO-BLK-SEQ-01 Instructions in order, Level 1–4, Coding. Planned.
  2. CO-BLK-SEQ-01Instructions in orderCoding · Primary 1 to Primary 4 (Level 1–4) · Planned
  3. CO-BLK-LOP-01 Repeat blocks, Level 3–5, Coding. Sample lesson in the demo.
  4. CO-BLK-LOP-01Repeat blocksCoding · Primary 3 to Primary 5 (Level 3–5) · Sample lesson in the demo Needs Instructions in order (required).Try the sample lesson: Repeat blocks
  5. DS-CMP-TYP-01 The home row, Level 3–6, Digital skills. Planned.
  6. DS-CMP-TYP-01The home rowDigital skills · Primary 3 to Primary 6 (Level 3–6) · Planned · recommended
  7. CO-BLK-CND-01 If this, then that, Level 3–6, Coding. Planned.
  8. CO-BLK-CND-01If this, then thatCoding · Primary 3 to Primary 6 (Level 3–6) · Planned · recommended
  9. CO-BLK-LOP-02 Patterns with loops, Level 4–6, Coding. Planned.
  10. CO-BLK-LOP-02Patterns with loopsCoding · Primary 4 to Primary 6 (Level 4–6) · Planned Needs Repeat blocks (required).
  11. MA-ARI-ORD-01 Order of operations, Level 5–6, Maths. Planned.
  12. MA-ARI-ORD-01Order of operationsMaths · Primary 5 to Primary 6 (Level 5–6) · Planned · recommended
  13. CO-BLK-LOP-03 Loops inside loops, Level 5–7, Coding. Planned.
  14. CO-BLK-LOP-03Loops inside loopsCoding · Primary 5 to JSS 1 (Level 5–7) · Planned · recommended
  15. CO-PRG-PYB-01 Your first Python program, Level 7–9, Coding. Planned.
  16. CO-PRG-PYB-01Your first Python programCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Planned Needs Patterns with loops (required), The home row (recommended).
  17. CO-PRG-PYB-02 Variables, Level 7–9, Coding. Sample lesson in the demo.
  18. CO-PRG-PYB-02VariablesCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Sample lesson in the demo Needs Your first Python program (required).Try the sample lesson: Variables
  19. CO-PRG-PYB-03 Numbers and calculations, Level 7–9, Coding. Planned.
  20. CO-PRG-PYB-03Numbers and calculationsCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Planned Needs Variables (required), Order of operations (recommended).
  21. MA-ALG-FRM-01 Substituting into formulae, Level 7–8, Maths. Planned.
  22. MA-ALG-FRM-01Substituting into formulaeMaths · JSS 1 to JSS 2 (Level 7–8) · Planned · recommended
  23. CO-PRG-PYB-05Decisions with ifCoding · JSS 2 to SSS 1 (Level 8–10) · Planned Needs Numbers and calculations (required), If this, then that (recommended).
  24. CO-PRG-PYB-06Loops in PythonCoding · JSS 2 to SSS 1 (Level 8–10) · Planned Needs Decisions with if (required), Loops inside loops (recommended).
  25. CO-PRG-PYF-01Defining functionsCoding · JSS 2 to SSS 2 (Level 8–11) · Planned Needs Loops in Python (required).
  26. CO-PRG-PYB-07ListsCoding · JSS 2 to SSS 1 (Level 8–10) · Planned Needs Loops in Python (required).
  27. CO-PRG-PYF-02Parameters and return valuesCoding · JSS 3 (BECE) to SSS 2 (Level 9–11) · Planned Needs Defining functions (required), Substituting into formulae (recommended).
  28. CO-ALG-SRT-01Linear searchCoding · JSS 3 (BECE) to SSS 2 (Level 9–11) · Planned Needs Parameters and return values (required), Lists (required).
  29. CO-PRG-PYF-03ScopeCoding · JSS 3 (BECE) to SSS 2 (Level 9–11) · Planned Needs Parameters and return values (required).
  30. CO-ALG-SRT-03Simple sortsCoding · SSS 1 to SSS 3 (WASSCE) (Level 10–12) · Planned Needs Linear search (required).
  31. CO-PRG-PYF-05RecursionCoding · SSS 2 to A level / JUPEB / foundation year (Level 11–13) · Planned Needs Scope (required).
  32. CO-ALG-SRT-04Merge sortCoding · SSS 2 to A level / JUPEB / foundation year (Level 11–13) · Planned · the destination Needs Simple sorts (required), Recursion (required).
21 stops across Coding, Digital skills and Maths. 2 have a sample lesson in the demo; the other 19 are planned and not yet written.

Help light the room where this is learned.

Every route on this map starts in a classroom with 24 stations, a tutor that works offline and a facilitator upstairs. Four are planned and waiting for light.

Help light a LanternTalk to us about a major gift