Scala Implementation of Insertion Sort

Introduction
Insertion sort is the best sorting algorithm for small-sized list of elements as compared to selection sort and bubble sort. This sorting algorithm always maintains a sorted sublist within an iteration i.e. it finds the correct position of a single element at a time and inserts it in its correct position within the currently sorted sublist.

Worst Complexity    : O(n*n)
Best Complexity       : O(n)
Average Complexity: O(n*n)

Implementation

package main.scala

object InsertionSort {

  val array = Array(0, 5, 2, 6, 3, 1)

  def main(args: Array[String]) {

    print("Unsorted List ")

    println(array.toList)

    print("Asceding sorted List ")

    insertionSortAscending;

    println(array.toList)

    insertionSortDescending

    print("Desceding sorted List ")

    println(array.toList)

  }

  def insertionSortAscending {
    //first element is considered as sorted sublist
    for (outer <- 1 until array.length) {

      var temp = array.apply(outer)

      var inner = outer - 1
      // temp < array.apply(inner) is used for Ascending sort
      while (inner >= 0 && temp < array.apply(inner)) {

        array.update(inner + 1, array.apply(inner))

        inner -= 1

      }

      array.update(inner + 1, temp)

    }

  }

  def insertionSortDescending {

    for (outer <- 1 until array.length) {

      var temp = array.apply(outer)

      var inner = outer - 1
      // temp > array.apply(inner) is used for Descending sort

      while (inner >= 0 && temp > array.apply(inner)) {

        array.update(inner + 1, array.apply(inner))

        inner -= 1

      }

      array.update(inner + 1, temp)

    }

  }
}

Input   :  0,5,2,6,3,1
Output:  0 1 2 3 5 6 (Ascending)
Output:  6 5 3 2 1 0 (Descending)

Conclusion
In this post, we learned the implementation of insertion sort in Scala language. Please leave your comments in the comments box. Thank you.