Insertion Sort Algorithm in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Insertion Sort Algorithm?

Insertion Sort builds the final sorted list one item at a time by taking each element and inserting it into its correct position among the already sorted elements.

beginner

How does Insertion Sort handle the elements during sorting?

It divides the list into a sorted and an unsorted part. It takes elements from the unsorted part and inserts them into the correct position in the sorted part.

intermediate

What is the time complexity of Insertion Sort in the worst case?

The worst-case time complexity is O(n²), where n is the number of elements. This happens when the list is sorted in reverse order.

intermediate

Why is Insertion Sort efficient for nearly sorted lists?

Because it only moves elements that are out of order, so if the list is almost sorted, fewer moves are needed, making it close to O(n) time.

beginner

Show the first step of Insertion Sort on the list [5, 3, 8, 6]. What does the list look like after inserting the second element?

After inserting 3 into the sorted part [5], the list becomes [3, 5, 8, 6].

What part of the list does Insertion Sort consider sorted at the start?

A The first element

B The entire list

C The last element

D No elements

Insertion Sort starts with the first element as the sorted part and inserts other elements into it.

Which of these best describes the way Insertion Sort moves elements?

A Swaps adjacent elements repeatedly

B Divides the list and merges sorted parts

C Selects the smallest element and swaps it with the first unsorted element

D Inserts elements into their correct position by shifting larger elements right

Insertion Sort shifts larger elements to the right to make space for the element being inserted.

What is the best-case time complexity of Insertion Sort?

A O(n²)

B O(n)

C O(log n)

D O(n log n)

When the list is already sorted, Insertion Sort only makes one pass, resulting in O(n) time.

Which scenario causes Insertion Sort to perform the most operations?

A List is already sorted

B List has all equal elements

C List is sorted in reverse order

D List is randomly ordered

Reverse order requires maximum shifting of elements, causing worst-case O(n²) time.

What is the main advantage of Insertion Sort compared to more complex algorithms?

A It uses less memory and is simple to implement

B It is always faster than other algorithms

C It sorts in parallel

D It never requires shifting elements

Insertion Sort is simple and uses minimal extra memory, making it good for small or nearly sorted lists.

Explain how Insertion Sort processes a list step-by-step.

Think about dividing the list into sorted and unsorted parts.

Describe the time complexity of Insertion Sort and when it performs best and worst.

Consider how many shifts are needed in different list orders.