Home›Study Resources›Computer Science›
How does a merge sort work?
Computer Science
A-Level

How does a merge sort work?

A merge sort is a divide and conquer algorithm. It splits the list in half repeatedly until each sublist holds one item, then merges the sublists back together in order. Its time complexity is O(n log n). Example: Sort 6, 2, 9, 4 using a merge sort. Split: [6, 2] and [9, 4], then [6], [2], [9], [4]. Merge: [6] and [2] give [2, 6]; [9] and [4] give [4, 9]. Merge [2, 6] and [4, 9]: compare 2 and 4, then 6 and 4, then 6 and 9, then add 9. Answer: 2, 4, 6, 9

A merge sort is a divide and conquer algorithm. It splits the list in half repeatedly until each sublist holds one item, then merges the sublists back together in order. Its time complexity is O(n log n).

Worked example

Sort 6, 2, 9, 4 using a merge sort.

  1. Split: [6, 2] and [9, 4], then [6], [2], [9], [4].
  2. Merge: [6] and [2] give [2, 6]; [9] and [4] give [4, 9].
  3. Merge [2, 6] and [4, 9]: compare 2 and 4, then 6 and 4, then 6 and 9, then add 9.

Answer: 2, 4, 6, 9

Reviewed by

Want one-to-one support?

One-to-one online tuition can help you build confidence in your subject. Find a tutor who teaches your course.

Find a Tutor

Learn face to face in Glasgow

Prefer in-person lessons? Visit the ExpertTutor Glasgow Southside centre.

See the centre