UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 16.5 Free with a free account
Comparing Sorts: Speed, Memory, and Stability
Data Structures and Algorithms · Chapter 16: Sorting, Selection, and Text ProcessingSection 16.5 · lesson 71 of 8713 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: Finding Another Slot When the Home Slot Is Taken →← Insertion Sort: Sliding Each Element into PlaceNext lesson: Finding Another Slot When the Home Slot Is Taken →
In this lesson
How six sorts compare on time, memory, stability, and adaptivity.
- Compare six sorting algorithms on time, extra space, stability, and adaptivity
- Explain why selection sort, quicksort, and heap sort are not stable
- Derive the log of n factorial lower bound for comparison sorts with a decision tree
- Choose a sorting algorithm from a problem's requirements
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,934 words). Read along, or search it.
Opening Question
Bicycle, Van, or Sports Car
Which vehicle is best: a bicycle, a van, or a sports car? A bicycle is perfect for a short trip, a van carries the most, and a sports car is fastest on an open road. Nobody can answer without knowing where the journey goes. Sorting methods are the same. So which of the six sorts you've met is the best? By the end of this lesson, the honest answer will be: it depends, and you'll know on what.
Four Yardsticks
Time, Space, Stability, and Adaptivity
Here are the six: bubble, selection, insertion, merge, quick, and heap sort. They're compared on four yardsticks. Time: how many comparisons, and how many milliseconds. Extra space: how much memory beyond the array itself. Stability: whether equal keys keep their original order. And adaptivity: whether the sort does less work when the input is already nearly in order.
Test Setup
Packing Key and Position Into a Long
A fair test needs the same rules for every sort. Every comparison between two keys goes through one small method that counts it. Each element packs its key into the high thirty-two bits of a long, and its original position into the low thirty-two bits. The sorts compare only the key part. So afterward, the positions reveal whether equal keys stayed in their original order. Five kinds of input were used, two thousand keys each: random, already sorted, reversed, nearly sorted, and few distinct values, only zero to nine.
Comparison Counts
Simple Sorts Versus the Fast Group
Here are the comparisons each sort needed, for three of the inputs. Two groups are obvious at a glance. The three simple sorts range from under two thousand to nearly two million, depending on the input. Merge, quick, and heap sort stay between about eleven thousand and forty-seven thousand on every input. Selection sort is the most predictable of all. It makes exactly one million, nine hundred ninety-nine thousand comparisons, whatever the input, because it always scans the whole unsorted part.
Growth Rates
What Doubling the Data Reveals
Now double the data. From eight thousand to sixteen thousand random keys, bubble sort's comparisons grew by a factor of four. Merge sort's grew by two point two. That's the practical meaning of order n squared against order n log n. Timed on one machine, at forty thousand keys, bubble sort took about two and a half seconds. Heap sort took about four milliseconds, roughly six hundred times faster. At a million keys, only the fast group is practical. And merge sort, with the fewest comparisons, wasn't the fastest. It also copies every key through a helper array. Comparisons and milliseconds answer different questions, so both are worth knowing.
Extra Space
Helper Arrays and Recursion Stacks
Extra space is memory beyond the array being sorted. Bubble, selection, insertion, and heap sort move keys inside the array, so they need only a few variables. Merge sort needs a helper array as long as the data. For a million keys, that's a million extra cells, doubling the memory used for the data. Quicksort uses no helper array, but its recursion needs stack space. For a million random keys, the deepest recursion was forty levels, which is why its space is called order log n. That depends on good splits, or on recursing on the smaller side first. Heap sort needs no extra array at all, and that, with its guaranteed time, is its selling point.
Stability
One Long Swap Reverses Equal Keys
A sort is stable if records with equal keys leave in the same relative order they entered. That matters whenever records are sorted more than once. Sort employees by name, then by department. With a stable sort, each department is still in name order. With an unstable sort, the second pass can scramble the names, and the first sort's work is lost. A tiny example shows how stability breaks. Records A, B, and C have keys three, three, and one. Selection sort finds C, the smallest, at the end, and swaps it with A at the front. That one long swap carries A past B, and their order is reversed. Insertion sort only slides keys past strictly larger ones, so it never jumps over an equal key. A keeps its place in front of B.
Stability Verdict
Three Stable Sorts and Three Unstable
The same check, on two thousand records with only ten distinct keys, gave this verdict for all six. Bubble, insertion, and merge sort are stable. They only move a key past strictly larger keys, or take the left key first on ties. Selection, quick, and heap sort are not. They exchange keys that are far apart, and such an exchange can jump a key over an equal one. An unstable sort can be made stable by adding the original position as a tie-breaker. That's exactly what the packed positions allow, but it costs memory or time.
Quick Check
Selection Sort on Two Equal Keys
Quick check. Selection sort, exactly as written, runs on four new records: P with key two, Q with key five, R with key two, and S with key one. Afterward, which of the two records with key two comes first? Pause, and predict. R moves to the front of the pair. Step one finds S, the smallest, and swaps it with P at the front, which throws P to the very end. Step two picks R, then step three picks P. The order of the two equal keys is reversed. And the run never varies: the same input always gives the same result.
Adaptivity
Doing Less Work on Ordered Input
A sort is adaptive if it does less work when the input is already partly in order. Insertion sort is the clear winner on truly ordered data. On sorted input it needs one thousand, nine hundred ninety-nine comparisons, against nearly a million on random input. But its cost is about n plus the number of out-of-order pairs. Twenty random swaps moved some keys far from home, and it needed thirty thousand comparisons: twice merge sort's. Bubble sort's early exit only helps on perfectly sorted data. A small key far to the right moves one place per pass, so the exit never triggers. Merge sort saves about forty-three percent on sorted data, but its growth rate doesn't change, so it's only slightly adaptive. Selection, quick, and heap sort aren't adaptive at all.
Decision Trees
Questions, Branches, and Leaves
Could someone invent a comparison sort that beats merge sort by a wide margin? No. And the reason is counting, not a lack of cleverness. A comparison sort learns about the data only by asking: is a less than b? Each answer is yes or no. Draw every question an algorithm might ask while sorting three keys, a, b, and c. Each box is a question, and each branch is an answer. Each leaf at the bottom is the final order the algorithm announces. This picture is a decision tree. Six orders need six leaves, and the longest path here asks three questions.
Lower Bound
Proving the Comparison Sort Limit
The argument has three steps. Three keys can be arranged in three factorial, six, different orders, and the algorithm must be able to announce every one. So the tree needs at least six leaves. Second, each question at most doubles the number of branches. A tree with at most h questions on any path has at most two to the h leaves. Two questions give only four leaves, too few. So some input must take three comparisons. Third, for n keys the tree needs n factorial leaves, so the worst case takes at least log base two of n factorial comparisons. Half the factors of n factorial are at least n over two. So that log is at least n over two, times log of n over two, which grows like n log n. Every comparison sort needs on the order of n log n comparisons in the worst case. That's written omega of n log n.
Exact Floor
How Close Real Sorts Come to the Floor
The floor was computed exactly, and checked against the worst cases of merge sort and insertion sort, over every possible ordering of a few keys. For three keys, the floor is three, and both sorts reach it. For four keys, the floor is five. Merge sort needs five, and insertion sort six. For eight keys, the floor is sixteen. Merge sort needs seventeen, while insertion sort's worst case has pulled away to twenty-eight. At a million random keys, merge sort came within one percent of the floor. Quicksort used about fifty-three percent more, and heap sort about twice as many. They're still order n log n, since the bound limits only the growth rate. Their speed per comparison, and no extra memory, make up the difference.
Quick Check
Fewest Comparisons for Six Keys
Quick check. Six keys must be sorted by comparisons alone. What's the fewest comparisons any algorithm can promise for its worst case? Pause, and decide. Ten. Six keys have seven hundred twenty possible orders. Nine questions give at most five hundred twelve leaves, which is too few. Ten questions give one thousand twenty-four, which is enough. Eleven is what merge sort actually needs for six keys, one above the floor.
Cautions
Where the Lower Bound Does Not Apply
Two cautions keep the bound in perspective. It applies only to sorts that compare keys. A sort that uses the structure of the keys, such as counting how many times each small whole number occurs, isn't bound by it, and can run in time proportional to n. And it describes the worst case. That's why an adaptive sort like insertion sort can finish in n minus one comparisons on sorted input.
Summary Table
No Sort Wins Every Column
Here's everything in one place. Read it by column. Only merge sort and heap sort promise n log n in the worst case. Quicksort's worst case assumes poor pivots, which a random or median-of-three pivot makes unlikely. Only merge, insertion, and bubble sort are stable. And only merge sort pays order n in extra memory. No sort wins every column, and that's exactly why you need a guide.
Decision Guide
Rule Out Options Before Speed
Work through these questions from the top. The properties that rule out options come first, and speed comes last. Only a few dozen keys, or every key already close to its place? Insertion sort. Must records keep their order for equal keys? Merge sort: stable, and n log n in every case. A hard worst-case limit, and very little spare memory? Heap sort, as long as stability doesn't matter. A large array of plain values, where typical speed matters most? Quicksort, with a safe pivot rule. And small whole-number keys in a narrow range? A counting-style sort.
In Practice
What Java's Library Sorts Choose
Professional libraries reason the same way. In Java, Arrays dot sort on an array of primitive values uses a tuned dual-pivot quicksort. Stability is meaningless there, because equal ints can't be told apart, and speed matters most. On an array of objects, equal keys can belong to different records. So the library uses a stable sort, built from merge sort and insertion sort ideas. And it benefits when the data is already partly in order. In the million-key test, Java's own sort was the fastest: seventy-nine milliseconds, against one hundred thirty-eight for the hand-written quicksort. So use the library sort, and understand these trade-offs for when stability, memory, or a worst-case guarantee rules out the default.
Key Takeaways
Six Sorts Compared
To sum up. Bubble, selection, and insertion sort grow quadratically. Merge, quick, and heap sort grow as n log n. Merge sort needs order n extra memory but is stable. Heap sort needs none but isn't stable. Insertion sort is strongly adaptive on data that's nearly in order. Every comparison sort needs at least log of n factorial comparisons in the worst case, and merge sort comes within one percent. Choose by requirements first, and by speed last.
Think About It
Sorting Five Million Orders by Date
Here's something to think about. A warehouse sorts five million orders by date. Orders on the same date must stay in arrival order, and the list arrives mostly sorted. Weigh insertion sort, quicksort, and the library's object sort. Which would you choose, and which property rules out each of the others?
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 Comparing Sorts: Speed, Memory, and Stability
Which sorting algorithms are stable?
Why can't a comparison sort beat n log n?
What is the minimum number of comparisons needed to sort six elements?
How do you choose the right sorting algorithm?
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 →