Ühendasorteerimine

Ühendasorteerimine, also known as merge sort, is a comparison-based sorting algorithm. It employs a divide and conquer strategy, breaking down the input array into smaller subarrays. These subarrays are then recursively sorted, and subsequently merged back together in a sorted manner. The fundamental operation of merge sort is the merge step, where two already sorted subarrays are combined into a single sorted array. This merging process typically involves comparing elements from the two subarrays and placing the smaller element into the new merged array until all elements from both subarrays are exhausted. The algorithm's time complexity is consistently O(n log n) in all cases, making it efficient for large datasets. Its space complexity is O(n) due to the need for auxiliary space during the merging process. While not in-place, merge sort is stable, meaning that elements with equal values maintain their relative order in the sorted output. This property makes it suitable for situations where maintaining original order for duplicate items is important. Ühendasorteerimine is widely used in various computing applications, including library sorting functions and external sorting where data does not fit into memory.