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.
/**
* This file is part of Scalacaster project, https://github.com/vkostyukov/scalacaster
* and written by Vladimir Kostyukov, http://vkostyukov.ru
*
* Merge Sort http://en.wikipedia.org/wiki/Mergesort
*
* Worst - O(n log n)
* Best - O(n log n)
* Average - O(n log n)
*
* -Notes-
*
* Using mergesort is a common way to sort a singly-linked list in a functional environment.
* This implementation fits into standard requirements about performance. The only difference
* here with default imperative implementation is a way how to split a list into two parts.
* This commonly solved by using length of the list, which costs O(n) since requires to walk
* from the start to the end of this. In this implementation, list is splitted into two equal
* parts by using 'halfify' function. This function perform very simple thing - it takes first
* two elements of the list and appends them to two separate lists, which accumulate the result.
* In other words, this function append all even nodes into first part, while odd nodes into the
* second one. This can be done in O(n).
*/
def mergesort[A <% Ordered[A]](list: List[A]): List[A] = {
def sort(p: (List[A], List[A])): List[A] = p match {
case (Nil, Nil) => Nil
case (ha :: Nil, Nil) => ha :: Nil
case (Nil, hb :: Nil) => hb :: Nil
case (as, bs) => merge(halfifyAndSort(as), halfifyAndSort(bs))
}
def halfify(as: List[A]): (List[A], List[A]) = {
def loop(bs: List[A], fs: List[A], ss: List[A]): (List[A], List[A]) = bs match {
case f :: s :: r => loop(r, f :: fs, s :: ss)
case f :: Nil => (f :: fs, ss)
case Nil => (fs, ss)
}
loop(as, Nil, Nil)
}
def merge(as: List[A], bs: List[A]): List[A] = {
def loop(cs: List[A], ds: List[A], r: List[A]): List[A] = (cs, ds) match {
case (ha :: ta, hb :: tb) =>
if (ha < hb) loop(ta, ds, ha :: r)
else loop(cs, tb, hb :: r)
case (ha :: ta, Nil) => loop(ta, Nil, ha :: r)
case (Nil, hb :: tb) => loop(Nil, tb, hb :: r)
case (Nil, Nil) => r
}
loop(as, bs, Nil).reverse
}
def halfifyAndSort(as: List[A]) = sort(halfify(as))
halfifyAndSort(list)
}
