Merge Sort

Learn about merge sort, a divide-and-conquer algorithm, which breaks items into smaller elements until sorting them becomes really simple.

Merge Sort: Conceptual

Lesson 1 of 2

1
Merge 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...
2
Merge 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...
3
When merging larger pre-sorted lists we build the list similarly to how we did with single-element lists. Let's call the two lists [...] and [...] . Both [...] and [...] are already sorted....
4
Merge sort was unique for its time in that the best, worst, and average time complexity are all the same: [...] . This means an almost-sorted list will take the same amount of time as a completely...

1
What 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 ...
2
How 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.
3
Our [...] 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, we're ...
4
Now we need to build out our result list. When we're merging our lists together, we're creating ordered lists that combine the elements of two lists.
5
Since we've only technically depleted one of our two inputs to [...] , we want to add in the rest of the values to finish off our [...] function and return the sorted list.
6
Let's update our [...] function so that it returns a sorted list finally!
7
We've written our merge sort! The whole sort takes up two functions: [...] which is called recursively breaks down an input list to smaller, more manageable pieces. [...] which is a helper fu...

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory