ArraysLesson 11Free preview

DSA Merge Sort

This lesson is part of DSA · All levels

Summary

Merge sort divides the list into two parts until each contains one element, and then re-assembles them in order. The process of merging compares the front elements of each piece so that it always produces the correct order. This algorithm is stable and consistent, but requires additional memory as much as data.

Key points

Strategy of divide and conquer: divide, arrange recursively, then join
Always at the best, average, and worst.
It's stable so it's safe for data with twin values.
Requires additional memory for the merge stage

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.