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.
- 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
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 TutorLearn face to face in Glasgow
Prefer in-person lessons? Visit the ExpertTutor Glasgow Southside centre.
See the centre