Recursive Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. However, insertion sort provides several advantages: 1. Simple implementation: Jon Bentley shows a three-line c version, and a five-line optimized version Efficient for (quite) small data sets, much like other quadratic sorting algorithmsAdaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each component in the input is no more than K places away from its sorted position 2. Stable; i.e., makes not change the relative order of components with equal keys
package Sort

object RecursiveInsertionSort {

  /**
    *
    * @param array - a List of unsorted integers
    * @return - sequence of sorted integers @array
    */
  def recursiveInsertionSort(array: List[Int]): List[Int] = {

    def insertion(x: List[Int]): List[Int] = {
      x match {
        case List() => List()
        case x :: xs => ins(x, insertion(xs))
      }
    }

    def ins(x: Int, xs: List[Int]): List[Int] = {
      xs match {
        case List() => List(x)
        case x2 :: xs2 => if (x <= x2) x :: xs else x2 :: ins(x, xs2)
      }
    }

    insertion(array)
  }
}

LANGUAGE:

DARK MODE: