What is the basic insertion method (insertion sort)? A sorting algorithm that inserts elements in the proper position in the aligned part

What is the basic insertion method?

The basic insertion method, also known as insertion sort, is a simple and efficient sorting algorithm that works by dividing the input list into two parts: a sorted part and an unsorted part. It repeatedly selects an element from the unsorted part and inserts it into its correct position in the sorted part until the entire list is sorted.

How does the basic insertion method work?

1. Start with the second element in the list and consider it as the first element in the sorted part.
2. Compare this element with the elements in the sorted part, moving from right to left, until an element smaller than it is found.
3. Insert the element in its correct position by shifting the larger elements one position to the right.
4. Repeat steps 2 and 3 for the remaining unsorted elements until the list is fully sorted.

Example:
Let’s understand the basic insertion method with an example. Consider the following unsorted list:

We start with the second element, ‘2’, and compare it with the first element, ‘5’. Since ‘2’ is smaller than ‘5’, we shift ‘5’ one position to the right and insert ‘2’ at its correct position in the sorted part. Now the modified list becomes:

Next, we move to the third element, ‘4’, and compare it with the elements in the sorted part (2 and 5). ‘4’ is placed in the correct position, resulting in:

We continue this process for the remaining elements until the list is sorted. The final sorted list is:

Advantages and disadvantages of the basic insertion method

The basic insertion method comes with its own set of advantages and disadvantages:

Advantages:
1. Simple implementation: The algorithm is straightforward and easy to understand.
2. Efficient for small datasets: It has good performance for small lists or datasets that are almost sorted.
3. In-place sorting: It does not require additional memory space as it operates directly on the input list.

Disadvantages:
1. Inefficiency for large datasets: The algorithm’s time complexity is O(n^2), making it inefficient for large datasets.
2. Not suitable for highly unsorted lists: It may require a large number of shifts when dealing with a highly unsorted list.

The basic insertion method, despite its limitations, remains a useful sorting algorithm, particularly for small lists or partially sorted datasets. Understanding its mechanics can provide a foundational knowledge of sorting algorithms and their implementations.

Reference Articles

Reference Articles

Read also

[Google Chrome] The definitive solution for right-click translations that no longer come up.