Compare Insertion Sort

How does Insertion Sort compare with other sorting algorithms? Let's analyze its strengths and weaknesses.

Insertion Sort vs. Bubble Sort

• Time Complexity: Both have O(n²) average and worst case, but insertion sort typically performs fewer comparisons.
• Efficiency: Insertion sort is generally more efficient than bubble sort.
• Adaptivity: Both are adaptive, but insertion sort adapts better to partially sorted arrays.
• Use Case: Insertion sort is usually preferred over bubble sort in practice.

Insertion Sort vs. Selection Sort

• Time Complexity: Both have O(n²) average and worst-case complexity.
• Swaps: Selection sort makes fewer swaps (O(n)) while insertion sort can make up to O(n²) shifts.
• Adaptivity: Insertion sort is adaptive while selection sort is not.
• Stability: Insertion sort is stable while selection sort is not.
• Performance: Insertion sort outperforms selection sort when the array is nearly sorted.

Insertion Sort vs. Merge Sort

• Time Complexity: Merge sort is consistently O(n log n), while insertion sort is O(n²) in average and worst cases.
• Space Complexity: Insertion sort is in-place (O(1)) while merge sort requires additional O(n) space.
• Use Case: Merge sort is better for large datasets, while insertion sort can be faster for small or nearly sorted arrays.
• Stability: Both are stable sorting algorithms.

Insertion Sort vs. Quick Sort

• Time Complexity: Quick sort has O(n log n) average case but O(n²) worst case, while insertion sort has O(n²) average case.
• Space Complexity: Both can be implemented as in-place algorithms, though quick sort uses O(log n) stack space.
• Adaptivity: Insertion sort is adaptive while basic quicksort is not.
• Stability: Insertion sort is stable while quick sort is not.
• Use Case: Quick sort is generally much faster for large random arrays, while insertion sort can be quicker for small or nearly sorted arrays.

When to Choose Insertion Sort

• When the input size is small (typically less than 20 elements)
• When the array is already partially sorted
• When memory usage is a concern
• When stability is required
• As a component in other algorithms (e.g., Timsort uses insertion sort for small subarrays)