Insertion Sort

What is Insertion Sort?

Insertion sort is a sorting algorithm, which arranges elements present in an array in specific order such as ascending or descending.

Characteristics of Insertion sort

• Time Complexities

  • Worst Case: O(n*n)

  • Average Case: theta(n*n)

  • Best Case: Omega(n)

• Space Complexities

  • Worst Case: O(1)

• In place: Yes

• Stable: Yes

Java Implementation of Insertion sort