Merge Algorithm
The Merge K Sorted Linkedlists Algorithm is an efficient technique used to combine multiple sorted linked lists into a single, sorted linked list. This algorithm is particularly useful in scenarios where a large data set is divided into smaller, sorted linked lists, and the goal is to merge them together while maintaining the sorted order. The basic idea behind the algorithm is to compare the smallest (or largest, depending on the sort order) elements from each of the individual linked lists, and then merge them together to form a new, sorted linked list. This process is repeated until all the elements from the given linked lists are included in the final, merged linked list.
There are several approaches to implement the Merge K Sorted Linkedlists Algorithm, one of which is the divide and conquer method. In this approach, the problem of merging K sorted linked lists is divided into smaller subproblems, where pairs of linked lists are merged together using a standard two-pointer merge algorithm for sorted linked lists. This process is carried out in a hierarchical manner, with the results from the lower levels being combined and merged at higher levels, until a single, sorted linked list is obtained. Another approach is to use a min-heap or priority queue, which stores the smallest (or largest) element from each individual linked list. The algorithm then extracts the minimum (or maximum) element from the heap, appends it to the merged linked list, and inserts the next element from the same linked list into the heap. This process continues until all the elements are processed, resulting in a single, sorted linked list. Overall, the Merge K Sorted Linkedlists Algorithm is an effective and versatile method for combining multiple sorted linked lists into a single sorted list.
package org.gs.sort
import math.Ordering
import scala.annotation.tailrec
/** Divide list in 2 then sort each half, recursively
*
* This is uses an example from Stack Overflow instead of translating from Algorthms
*
* @see [[http://stackoverflow.com/questions/2201472/merge-sort-from-programming-scala-causes-stack-overflow]]
* @see [[https://algs4.cs.princeton.edu/22mergesort/Merge.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
object Merge {
/** Recursive mergesort
*
* @tparam A generic element
* @param xs list of elements to sort
* @param ord implicit ordering of type A
* @return sorted list
*/
def msort[A](xs: List[A])(implicit ord: Ordering[A]): List[A] = {
/** returns if a less than b */
def less(a: A, b: A): Boolean = ord.lt(a, b)
@tailrec /** prepend smaller element to accumulator then return it when one half is empty */
def merge(xs: List[A], ys: List[A], acc: List[A]): List[A] = (xs, ys) match {
case (Nil, _) => ys.reverse ::: acc
case (_, Nil) => xs.reverse ::: acc
case (x :: xs1, y :: ys1) =>
if (less(x, y)) merge(xs1, ys, x :: acc) else merge(xs, ys1, y :: acc)
}
val n = xs.length / 2
if (n == 0) xs else {
val (ys, zs) = xs splitAt n
merge (msort(ys), msort(zs), Nil).reverse
}
}
}
