sisestussorteerimine

Sisestussorteerimine, known in English as insertion sort, is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: it is simple to implement, efficient for small data sets, and efficient for data sets that are already substantially sorted.

The algorithm works by iterating through the input array and, for each element, finding the correct position within the already sorted portion of the array and inserting it there. This process continues until the entire array has been iterated through. At each step, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats this process until no input elements remain. The resulting list is sorted.

Insertion sort is an in-place sorting algorithm, meaning it does not require additional memory space proportional to the input size. Its time complexity in the worst and average case is O(n^2), where n is the number of elements to be sorted. However, in the best case, when the input array is already sorted, its time complexity is O(n). This makes it a practical choice for small arrays or for arrays that are nearly sorted.