What is the working mechanism of Insertion Sort, and what is the origin of its name?

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Is insertion sort a stable, in-place sorting algorithm or an out-of-place sorting algorithm?

Insertion sort is a stable in-place algorithm, meaning that it does not require any extra space and maintains the relative order of duplicates.

How does the number of elements impact the efficiency of insertion sort?

The efficiency of insertion sort is impacted by the size of the input list, and as the list size increases, the number of iterations needed for the algorithm to sort the list also increases, which can result in poor performance when sorting large lists, making it unsuitable for large-scale applications.

What are advantages and disadvantages of insertion Sort?

Advantages:

• Insertion sort is easy to understand and implement.
• It does not require any additional memory space.
• It's adaptability to different types of data.
• It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative order in the sorted output.

Disadvantages:

• Insertion sort has a time complexity of O(n^2) which makes it very slow for large data sets.
• It is not efficient for large data sets, because it requires multiple passes through the data.