UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 16.4 Free with a free account
Insertion Sort: Sliding Each Element into Place
Data Structures and Algorithms · Chapter 16: Sorting, Selection, and Text ProcessingSection 16.4 · lesson 70 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: Comparing Sorts: Speed, Memory, and Stability →← Choosing a Pivot and Partitioning Everything Around ItNext lesson: Comparing Sorts: Speed, Memory, and Stability →
In this lesson
How insertion sort slides each key into a sorted left part.
- Trace insertion sort pass by pass and count its comparisons and shifts
- Relate the number of shifts to the number of inversions in an array
- Explain insertion sort's best, average, and worst-case costs
- Explain why hybrid sorts finish small or nearly sorted pieces with insertion sort
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,541 words). Read along, or search it.
Opening Question
Sorting a Hand of Playing Cards
Pick up playing cards one at a time, and keep your hand in order. You don't re-sort the whole hand for each new card. You take the new card, slide it left past every card that's bigger, and let go. That habit is a sorting method, called insertion sort. So how much work does it cost? And when is it almost free?
Core Idea
Lift, Shift, and Drop the Key
Insertion sort splits the array into two parts. The sorted part is on the left, and it starts as just the first element. The unsorted part is on the right. Each pass takes the first element of the unsorted part, called the key, and inserts it into the sorted part. One pass has three moves. Lift the key out of its slot, and keep it in a variable. Shift every larger element of the sorted part one place to the right. Stop at the first element that's not larger, or at the left end. Then drop the key into the gap that the shifting opened. The sorted part is now one element longer.
Java Code
Save the Key and Check j First
In Java, the whole sort is a few lines. The outer loop picks the key, starting from the second element. Three details are worth a close look. First, the key is saved before anything moves, because the first shift overwrites its slot. Second, the order of the test matters. j greater than or equal to zero is checked before a of j is read. Swap the two conditions, and the loop reads a of minus one, and throws an ArrayIndexOutOfBoundsException, whenever the key is the smallest so far. Third, each step is a single write: a of j is copied into the next slot. The key is written only once, at the end.
Correctness
Why the Sorted Part Stays Sorted
Why does it work? Before each pass, the first i elements are in sorted order. The pass puts the key into the right place among them, so afterward one more element is sorted. When i reaches the end, everything is. The code was also tested on twenty thousand random arrays, many full of duplicates, and every result matched Java's own Arrays dot sort.
Worked Example
Eleven Comparisons and Eight Shifts
Now trace a whole sort of six, three, eight, two, seven, four. Pass one: the key three is compared once and shifts six. Pass two: eight is already larger than everything before it. One comparison, nothing moves. Pass three is the opposite. Two is smaller than everything, so it's compared with all three elements and slides to the front. Pass four: seven makes two comparisons and shifts one. Pass five: four makes four comparisons and shifts three. In all, eleven comparisons and eight shifts.
Inversions
Shifts Equal the Number of Inversions
Those eight shifts aren't a coincidence. A pair of elements is an inversion if the larger one comes first. The array six, three, eight, two, seven, four has exactly eight inversions: six with three, two and four, three with two, eight with two, seven and four, and seven with four. Each shift moves one element past one larger neighbor, so it removes exactly one inversion. The number of shifts equals the number of inversions. That was checked on eight different arrays of a thousand elements, and it held every time.
Stability
Strict Greater-Than Keeps Equal Scores in Order
Insertion sort works in place. Besides the array, it needs only the key and an index, so its extra memory doesn't grow with n. It's also stable: records with equal keys stay in their original order. Here, six people are sorted by score. With the strict greater-than in the loop, the three people who scored eighty, Ava, Cy, and Fay, keep their order. Write greater-than-or-equal instead, and an element equal to the key gets shifted too. The eighties come out reversed: Fay, Cy, Ava. The result is still in score order either way. Only the strict version keeps the earlier order among equals.
Quick Check
Counting Shifts on Six, Two, Five, One
Quick check. Insertion sort runs on a new array: six, two, five, one. How many shifts does it make in all? Pause, and decide. Five. Count the inversions: six is before two, five and one, then two before one, and five before one. That's five pairs. Six would be every pair out of order, a fully reversed array. Here, two comes before five, which is already in order.
Running Time
Sorted, Reversed, and Random Input
Its work is comparisons plus shifts, and both depend on the input, not just on n. Take a thousand elements in three situations. Best case: already sorted. Every key is larger than its left neighbor, so each pass makes one comparison and no shifts. That's nine hundred ninety-nine comparisons: order n. Worst case: reversed. Pass i shifts all i sorted elements, so the shifts add up to n times n minus one, over two: four hundred ninety-nine thousand, five hundred. Average case: in random data, about half of all pairs are out of order, so about a quarter of n squared shifts. Half the worst, but still order n squared.
Measurement
Timings That Match the Growth Rates
Timings on one machine show the same shapes. Each time n doubled, random and reversed input took about four times longer. That's the signature of order n squared. Reversed always took about twice as long as random, because it makes twice the shifts. When n doubled, sorted input took only twice as long, the signature of order n. At eighty thousand elements, the sorted array took about six thousand times less time than the random one.
Nearly Sorted Data
Cheap Fixes for Local Disorder
The best case isn't limited to perfectly sorted arrays. The cost is about n, plus the number of inversions. Move the last of a thousand elements to the front, and it costs only nine hundred ninety-nine shifts, against about a quarter million for random data. At a hundred thousand elements, swapping ten random pairs in a sorted array took a third of a millisecond to fix. Random data took five hundred seventy milliseconds. Local disorder is cheap too. When every element sat at most a hundred places from home, sorting a hundred thousand took about two milliseconds. That's why insertion sort is excellent for data that's almost in order, such as a sorted list with a few new records added.
Quick Check
Five New Records at the End
Quick check. A sorted list of a hundred thousand records gets five new records appended at the end, in no particular order. Insertion sort puts them in place. At most, about how many shifts can that take? Pause, and decide. About half a million, at most. Only the five new records move, and each can slide past at most the hundred thousand before it. Two and a half billion is the cost of sorting a hundred thousand random records, about five thousand times more. The sorted part never needs to move on its own.
Hybrid Sorts
Switching to Insertion Sort for Small Pieces
Its cost per element is about n over four shifts, so it grows with the size of the array. For large n, that's a disaster. For small n, it's tiny. Cutting a million random numbers into blocks of sixteen, an element moved fewer than four places on average. In blocks of two hundred fifty-six, about sixty-four. And insertion sort has almost no overhead: no recursion, no extra array, no calls in its inner loop. So a hybrid sort uses a fast divide-and-conquer method on large pieces, and switches to insertion sort when a piece gets small. With merge sort on a million numbers, cutoffs of sixteen to sixty-four ran about fifteen percent faster than no cutoff. A cutoff of five hundred twelve was slower than none. Java's own library does the same: its sorts finish short ranges with insertion sort.
Connection
Array Insertion With the Search Built In
Each pass is the array insertion you met with fixed-size arrays. To insert at a position, every element from there onward shifts one place right. The only new part is that the position isn't given. It's found while shifting, by comparing with the key. You could find the gap first and then move the block with System dot arraycopy. It gave the same results, and it wasn't faster. What costs time is how many elements move, not how they're moved. Finding the gap by binary search cut comparisons, for a thousand elements, from about two hundred fifty thousand, to under nine thousand. But the shifts stayed the same.
Common Mistakes
Five Ways to Get It Wrong
Five mistakes are common. Writing greater-than-or-equal: the sort still works, but it isn't stable. Testing a of j before checking j: it reads a of minus one, and throws. Forgetting to save the key: the first shift overwrites it, and the value is lost. Swapping neighbors step by step: a swap takes three writes, and a shift only one. And saying insertion sort is always order n squared. On sorted or nearly sorted data, it's order n.
Key Takeaways
Insertion Sort at a Glance
To sum up. Insertion sort keeps a sorted part on the left, and slides each next element into place. The shifts equal the inversions, and the comparisons add about one per pass. Best case order n on sorted data. Average and worst, order n squared. It's stable thanks to the strict greater-than, and it works in place. Small and nearly sorted inputs are its home, which is why hybrid sorts finish with it.
Think About It
New Contacts in a Sorted Phone List
Here's something to think about. Your phone's contact list is sorted by name, and you add three new contacts at the end. Which sort would you run, and roughly how much work would it do? What would change if the three were added at the front instead?
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 Insertion Sort: Sliding Each Element into Place
How does insertion sort work?
What is the time complexity of insertion sort?
Why is insertion sort fast on nearly sorted data?
What are common bugs in an insertion sort loop?
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 →