Lisäyslajittelu

Lisäyslajittelu, also known 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, it is efficient for small data sets, and it is efficient for data sets that are already substantially sorted.

The algorithm iterates through the input array, and for each element, it finds the correct position within the already sorted portion of the array and inserts it there. This process continues until all elements have been inserted into their correct positions, resulting in a fully sorted array. The key idea is to maintain a sorted sublist at the beginning of the array and incrementally expand it by taking elements from the unsorted part and inserting them into their proper place within the sorted sublist.

In terms of time complexity, insertion sort has an average and worst-case time complexity of O(n^2), where n is the number of elements in the array. This is because, in the worst case, each element might need to be compared with every element in the already sorted portion. However, its best-case time complexity is O(n) when the input array is already sorted, as each element is only compared once. Due to its quadratic time complexity in the average and worst cases, it is generally not recommended for large datasets. Nevertheless, it is often used as a subroutine in more advanced sorting algorithms like Timsort.