UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 16.2 Free with a free account
Merge Sort: Split in Half, Sort Each Piece, Combine
Data Structures and Algorithms · Chapter 16: Sorting, Selection, and Text ProcessingSection 16.2 · lesson 68 of 8710 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Choosing a Pivot and Partitioning Everything Around It →← Elementary Sorts: Bubble Sort and Selection SortNext lesson: Choosing a Pivot and Partitioning Everything Around It →
In this lesson
How merge sort divides, recurses, and merges in n log n time.
- Trace merge sort's divide, conquer, and combine steps on a small array
- Count the comparisons made when merging two sorted runs
- Derive merge sort's n log n running time with a recursion tree and by unrolling
- Explain merge sort's extra memory, its stability, and how it sorts linked lists
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,573 words). Read along, or search it.
Opening Question
Combining Two Sorted Piles of Papers
Someone hands you two piles of exam papers. Each pile is already in order, by student number. They want one ordered pile. Look at the top paper of each pile, take the smaller number, and repeat. You never go back, and each paper is handled once. So here's a question. If combining two sorted piles is that easy, can the same idea sort a pile that isn't sorted at all?
Three Steps
Divide, Conquer, and Combine
It can. Merge sort turns that observation into a complete sorting method, in three steps. Divide: split the collection into a left half and a right half. That only picks the middle. Nothing is compared. Conquer: sort each half, by applying the same method to it. That's recursion, on two problems of half the size. Combine: merge the two sorted halves into one sorted collection. That costs about one step per item. The halves are split again and again, until a piece has zero or one item. That's the base case: there's nothing left to sort.
Worked Example
Splitting Seven Numbers Down to Singles
Follow seven numbers through the whole method: 38, 27, 43, 3, 9, 82, and 10. The first split makes a left half of three numbers, and a right half of four. Each half splits again. Thirty-eight stands alone, and twenty-seven pairs with forty-three. On the right, three pairs with nine, and eighty-two with ten. One more round, and every piece holds a single number. Notice what didn't happen. Splitting never compared anything. It only decided where the middle is. And a piece of one item is already sorted. That's the base case, where the splitting stops.
Worked Example
Thirteen Comparisons to Merge Back
Now the pieces merge back. Each merge combines two runs, and a run is a stretch of items that's already in order. Merging twenty-seven with forty-three takes one comparison. Then thirty-eight joins them, in two more. On the right, three and nine merge in one comparison, and so do eighty-two and ten. Those two runs merge in two comparisons, into three, nine, ten, eighty-two. And the final merge combines the run of three with the run of four, in six comparisons. That's thirteen comparisons in all. Splitting did nothing but separate. All of the sorting happened as the pieces were merged.
Merge Step
A Marker on the Front of Each Run
Here's how one merge works. Keep a marker on the front item of each run. Compare the two marked items, copy the smaller into the output, and move that run's marker forward. Three against nine: three is copied. Twenty-seven against nine: nine goes. Twenty-seven against ten: ten goes. Twenty-seven against eighty-two: twenty-seven. Then thirty-eight, and forty-three, each smaller than eighty-two. Now the left run is used up, so eighty-two is copied with no comparison at all. Every comparison places one item for good, and the last item needs none. So merging n items takes at most n minus one comparisons: time proportional to n.
Java Code
A Five-Line Recursive Sort
Once merge is written, the sort itself is five lines of Java. The range lo to hi is half-open: hi is one past the last item. If the range holds fewer than two items, return. That's the base case. Otherwise, find the middle. Sort the left half by calling the same method, then sort the right half. Finally, merge the two halves. One scratch array, tmp, is created once at the top, and passed down to every call.
Running Time
A Recursion Tree With Log n Levels
How fast is it? Let T of n be the time to sort n items. Sorting means two sorts of half the size, plus a merge that costs about n. A single item costs nothing. Now draw one box for every call. At the top is one piece of size n, and merging it costs n. Below it are two pieces of half the size. Merging both costs n over two, twice, which is n again. Then four pieces of a quarter each: n in total, once more. Every level of this tree costs exactly n. The pieces halve at each level until they reach size one, which takes log base two of n halvings. So there are log n levels, each costing n, for a total of n log n.
Second Method
Unrolling the Recurrence
A second method gives the same answer: unrolling. Replace T of n over two by its own formula, and watch the pattern. Once gives four T of n over four, plus two n. Once more gives eight T of n over eight, plus three n. After j halvings, it's two to the j copies, plus j times n. The pieces reach size one when j is log n. Then the copies cost nothing, and the total is n log n. Both methods agree: merge sort runs in O of n log n time.
Measurement
Steady Cost on Every Input Order
Counting comparisons on real runs agrees. For these sizes, the worst case is exactly n log n, minus n, plus one. Already sorted input costs about half of the worst case, and no less. Merge sort stays within a factor of two of n log n, whatever the order. That steadiness is its main attraction. Now set it against a quadratic sort, such as insertion sort. On one hundred thousand random items, insertion sort needed more than two and a half billion comparisons. Merge sort needed about one and a half million.
Quick Check
Merging Two Short Runs
Quick check. Here are two new runs: four, eleven, twenty-five, and seven, eight, thirty, forty-one. Merging them, how many comparisons are made? Pause, and decide. Five. Four against seven, eleven against seven, eleven against eight, eleven against thirty, and twenty-five against thirty. Then the left run is used up, so thirty and forty-one are copied with no comparison. Six was tempting, because n minus one is the most a merge can ever need. It's a limit, and a merge often finishes early.
Memory Cost
Scratch Space and Recursion Depth
Merge sort pays for its speed in memory. The merge step can't safely write into the array it's reading. Copying an item from the right run into the front would overwrite an item not yet used. So it builds the merged run in tmp, then copies it back. How that scratch space is organized matters. Fresh arrays at every merge add up to n log n slots. One shared buffer needs only n. The recursion needs a stack too. But each call halves the range, so the calls nest only log n deep: ten for a thousand items, twenty for a million. A sort that needs only a constant amount of extra space is called in place. Merge sort on an array is not.
Stability
Ties Taken From the Left Run
Real data usually comes as records, and two records can have equal sort keys. Here, five students are sorted by grade only. A sort is stable if equal records stay in the order they had before sorting. With the merge step as written, Raj stays before Leo, and Ava, Mei, and Zoe keep their order. Change one character, less than or equal to strict less than, and each group comes out reversed. Taking from the left run on a tie keeps the original order, because every item in the left run came earlier in the input. That matters when you sort twice. Sort by name, then by grade with a stable sort, and each grade group stays in name order.
Linked Lists
Slow and Fast Markers Find the Middle
Merge sort suits linked lists well, because both of its tools are cheap there. Merging needs no scratch array. It only changes where each node's next reference points, and the nodes stay where they are. Splitting needs no index. Walk a slow marker one node at a time, and a fast marker two at a time. When the fast one reaches the end, the slow one is at the middle. Cut the chain there, sort both parts, and merge. Walking to the middle adds about n steps per level, so the total stays n log n. And with the same less-or-equal test, it's stable.
Comparison
Array Version Versus List Version
Side by side, the two versions take the same time, n log n, on every input. The array version needs a scratch array of n slots, while the list version relinks nodes in place. The array finds its middle with one line of arithmetic. The list walks half of its nodes to get there. Both recurse about log n deep, and both are stable when ties take the left item.
Quick Check
Recursion Depth for Fifty Million Records
Quick check. Fifty million records are sorted with the array version, using one shared buffer. About how deep does the recursion go? Pause, and decide. About twenty-six levels. Each call halves the range, and log base two of fifty million is about twenty-five point six. Twenty-five million would be the depth if each call removed only a couple of items. Merge sort always halves. And fifty levels would be enough for about a quadrillion records.
Key Takeaways
Merge Sort in Brief
To sum up. Merge sort splits a collection in half, sorts each half by recursion, and merges the halves. Merging two sorted runs of n items takes at most n minus one comparisons. There are log n levels, each costing n, so merge sort runs in n log n on every input. On an array it needs about n extra slots, and it's stable when ties take from the left. On a linked list, merging only relinks nodes, and slow and fast markers find the middle.
Think About It
Why Existing Order Goes Unused
Here's something to think about. On an array that's already sorted, a simple quadratic sort needs only about n comparisons. Merge sort still needs about n over two, times log n. Why can't merge sort take advantage of order that's already there? And would you choose it for nearly sorted data?
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Merge Sort: Split in Half, Sort Each Piece, Combine
How does merge sort work?
Why is merge sort O(n log n)?
How many comparisons does it take to merge two sorted lists?
Is merge sort stable and does it sort in place?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →