Merge Sort Algorithm
The Merge Sorted Array Algorithm is an efficient, stable, and comparison-based algorithm that is used to combine two or more sorted arrays into a single sorted array. This algorithm is a crucial part of the renowned Merge Sort, which is a divide-and-conquer sorting technique. The main idea behind the algorithm is to compare the first elements of the given sorted arrays and select the smallest element to be placed in the resulting merged array. This process is continued for the remaining elements in the given sorted arrays until all elements have been merged into the final sorted array. This algorithm is highly versatile and can be used to sort various data structures such as lists, arrays, and even large-scale data stored in databases or external storage.
The efficiency of the Merge Sorted Array Algorithm lies in its linear time complexity, which is O(n+m), where n and m are the lengths of the two sorted arrays being merged. This is because the algorithm only needs to perform a single pass through both input arrays to generate the merged array. To implement the algorithm, two pointers or indices are used: one for each of the input arrays. These pointers start at the beginning of their respective arrays and are incremented as the elements are compared and added to the merged array. When one of the pointers reaches the end of its array, the remaining elements from the other array are added directly to the merged array, as they are already sorted. This algorithm can be implemented in various programming languages and can be easily adapted to handle additional constraints such as duplicate elements or custom comparison functions.
package sort
/**
* This function implements Merge Sort
*
* @param array The array to be sorted
* It is a Divide and Conquer algorithm. It sorts the array by dividing it into two halves and comparing the elements.
*
* Worst-case performance O(n log n)
* Best-case performance O(n log n)
* Average performance O(n log n)
* Worst-case space complexity O(n)
*/
fun <T: Comparable<T>> mergeSort(array: Array<T>, start: Int, end: Int) {
val temp = arrayOfNulls<Comparable<*>>(array.size) as Array<T>
if (start < end) {
val mid = start + (end - start) / 2
mergeSort(array, start, mid)
mergeSort(array, mid + 1, end)
merge(array, temp, start, mid, end)
}
}
/**
* This function merges the two halves after comparing them
* @param array The array to be sorted
* @param temp The temp array containing the values
* @param start Starting index of the array
* @param mid Middle index of the array
* @param end Ending index of the array
*/
fun <T: Comparable<T>> merge(array: Array<T>, temp: Array<T>, start: Int, mid: Int, end: Int) {
System.arraycopy(array, start, temp, start, end - start + 1)
var i = start
var j = mid + 1
var k = start
while (i <= mid && j <= end) {
if (temp[i] < temp[j]) {
array[k++] = temp[i++]
} else {
array[k++] = temp[j++]
}
}
while (i <= mid) {
array[k++] = temp[i++]
}
while (j <= end) {
array[k++] = temp[j++]
}
}
