Merge Sort
Learn about merge sort, a divide-and-conquer algorithm, which breaks items into smaller elements until sorting them becomes really simple.
StartKey Concepts
Review core concepts you need to learn to master this subject
Merge Sort Merging
Merge Sort Merging
Merge Sort is a divide and conquer algorithm. It consists of two parts:
1) splitting the original list into smaller sorted lists recursively until there is only 1 element in the list, 2) merging back the presorted 1-element lists into 2-element lists, 4-element lists, and so on recursively.
The merging portion is iterative and takes 2 sublists. The first element of the left sublist is compared to the first element of the right sublist. If it is smaller, it is added to a new sorted list, and removed from the left sublist. If it is bigger, the first element of the right sublist is added instead to the sorted list and then removed from the right sublist. This is repeated until either the left or right sublist is empty. The remaining non-empty sublist is appended to the sorted list.
How you'll master it
Stress-test your knowledge with quizzes that help commit syntax to memory