The insertion sort is a simple and intuitive sorting algorithm in the field of data structures. It is widely used due to its efficiency and ease of implementation. In this article, we will explore what the insertion sort is, how it works, and its time complexity.
What Is the Insertion Sort?
The insertion sort is a comparison-based sorting algorithm that builds the final sorted array one item at a time. It works by dividing the input array into two parts: a sorted subarray and an unsorted subarray. Initially, the sorted subarray contains only the first element of the input array, while the unsorted subarray contains the remaining elements.
How Does Insertion Sort Work?
The insertion sort algorithm starts by taking an element from the unsorted subarray and placing it at its correct position in the sorted subarray. This process continues until all elements in the unsorted subarray are processed.
Let’s understand how this process works with an example:
- Consider an array: [5, 2, 4, 6, 1, 3]
- We start with the first element (5) as our sorted subarray.
- We take the second element (2) from our unsorted subarray.
- We compare it with each element in our sorted subarray (5).
- If any element in our sorted subarray is greater than our current element (2), we shift that element to the right to make space for our current element.
- In this case, we shift (5) to make space for (2).
- We insert (2) at its correct position in our sorted subarray.
After the first iteration, our sorted subarray becomes [2, 5], and our unsorted subarray becomes [4, 6, 1, 3].
We repeat this process for each element in the unsorted subarray until all elements are processed. This results in a fully sorted array.
Time Complexity
The time complexity of the insertion sort algorithm is O(n^2) in the worst case and O(n) in the best case. The worst case occurs when the input array is in reverse order, requiring maximum comparisons and shifting operations.
However, the insertion sort algorithm performs well for small input sizes or partially sorted arrays. It also has advantages over other sorting algorithms like bubble sort and selection sort when it comes to almost sorted or nearly sorted data.
In Conclusion
The insertion sort is a simple yet powerful sorting algorithm that can efficiently handle small input sizes and partially sorted arrays. It works by gradually building a sorted subarray by inserting elements from an unsorted subarray at their correct positions. While its time complexity is not as efficient as more advanced sorting algorithms like merge sort or quicksort, it has its own set of advantages that make it a practical choice in certain scenarios.