Nov
30
Merge Sort implementation in Scala
Hey there! Welcome to ClearUrDoubt.com. In this post, we will look at a Scala program to implement merge sort. Merge Sort is an efficient sorting algorithm. It uses Divide and Conquer algorithm technique. Let’s look at the sample program:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
package com.clearurdoubt /** * Merge Sort is a divide and conquer algorithm. * * We have to divide the initial list into two halves and sort those lists and merge them once they are sorted. * */ object MergeSort extends App { def mergeSort(input: List[Int]) : List[Int] = { val middle = input.length / 2 if(middle == 0) input else { def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match { case (Nil, ys) => ys case (xs, Nil) => xs case (x :: xs1, y :: ys1) => if (x < y) x :: merge(xs1, ys) // append x and merge(remaining elements of xs (i.e., xs1), ys) else y :: merge(xs, ys1) // append y and merge(xs , remaining elements of ys (i.e., ys1)) } val (left, right) = input splitAt middle // Split the list into two halves merge(mergeSort(left), mergeSort(right)) // Apply merge on the sorted halves } } val numbers = List(2, -4, 4, 6, 1) println("Input: " + numbers) println("Reversed: " + mergeSort(numbers)) } |