Merge Sort
Learn about merge sort, a divide-and-conquer algorithm, which breaks items into smaller elements until sorting them becomes really simple.
Start
Key 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.
Big-O Runtime for Merge Sort
Big-O Runtime for Merge Sort
The Merge Sort algorithm is divided into two parts. The first part repeatedly splits the input list into smaller lists to eventually produce single-element lists. The best, worst and average runtime for this part is Θ(log N). The second part repeatedly merges and sorts the single-element lists to twice its size until the original input size is achieved. The best, worst and average runtime for this part is Θ(N). Therefore, the combined runtime is Θ(N log N).
Merge Sort Implementation in Python
Merge Sort Implementation in Python
We can implement the Merge Sort algorithm in Python using two functions, merge_sort(lst), the main function and merge(left, right), a helper function.
- 1Merge sort is a sorting algorithm created by John von Neumann in 1945. Merge sort’s “killer app” was the strategy that breaks the list-to-be-sorted into smaller parts, sometimes called a _divide-an…
- 2Merge sorting takes two steps: splitting the data into “runs” or smaller components, and the re-combining those runs into sorted lists (the “merge”). When splitting the data, we divide the input t…
- 4Merge sort was unique for its time in that the best, worst, and average time complexity are all the same: Θ(N*log(N)). This means an almost-sorted list will take the same amount of time as a comple…
- 1What is sorted by a sort? A sort takes in a list of some data. The data can be words that we want to sort in dictionary order, or people we want to sort by birth date, or really anything else that …
- 2How do we break up the data in a merge sort? We split it in half until there’s no more data to split. Our first step is to break down all of the items of the list into their own list.
- 3Our merge_sort() function so far only separates the input list into many different parts — pretty much the opposite of what you’d expect a merge sort to do. To actually perform the merging, w…
- 5Since we’ve only technically depleted one of our two inputs to merge(), we want to add in the rest of the values to finish off our merge() function and return the sorted list.
- 6Let’s update our merge_sort() function so that it returns a sorted list finally!
- 7We’ve written our merge sort! The whole sort takes up two functions: merge_sort() which is called recursively breaks down an input list to smaller, more manageable pieces. merge() which is a help…
How you'll master it
Stress-test your knowledge with quizzes that help commit syntax to memory
Merge Sort
Start