Lisäysjärjestäminen

Lisäysjärjestäminen, a Finnish term, translates to "insertion sort" in English and refers to a simple sorting algorithm. It works by building a sorted array one item at a time. During the process, it takes elements from the unsorted input data and inserts them into their correct position within the already sorted portion of the array.

The algorithm iterates through the input list, considering one element at a time. For each element, it compares it with the elements in the sorted sublist that precedes it. If the current element is smaller than an element in the sorted sublist, it shifts the larger element one position to the right to make space for the current element. This process continues until the correct position for the current element is found, or the beginning of the sorted sublist is reached. The current element is then inserted into that position.

Lisäysjärjestäminen is an in-place sorting algorithm, meaning it does not require significant additional memory space beyond the input array itself. Its time complexity is generally O(n^2) in the average and worst cases, making it inefficient for large datasets. However, it performs well for small datasets or nearly sorted lists, where its complexity approaches O(n). It is also a stable sorting algorithm, meaning that elements with equal values maintain their relative order in the sorted output. Due to its simplicity and efficiency on small inputs, lisäysjärjestäminen is often used as a building block in more complex sorting algorithms, such as hybrid sorts.