Python DSALesson 111Free preview

Merge Sort

This lesson is part of Python · All levels

Summary

This lesson discusses Merge Sort, a divide and conquer algorithm that divides a list into two recursively to the size of one, and then combines it back into a sequential order. Merge sort is consistent in all cases so it is often used for large-scale data. The disadvantage is that it requires additional memory for the array while merging.

Key points

The merge sort stage: split the list into two, sort each one recursively, then merge.
The merge function combines two sorted lists into one sorted list by comparing the front element.
Complexity at best, average, or worst.
Merge sort is stable because the elements are kept in the same order when combined.
Requires additional memory so it is not fully in-place.

Full lesson

Code examples and quizzes

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