Getting Started - Insertion Sort http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A

Main.java

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int A[] = new int[100];

        for(int i=0;i<n;i++){
            A[i] = scan.nextInt();
        }

        for(int i=1;i<n;i++){
            printArray(A, n);
            int v = A[i];
            int j = i - 1;
            // 挿入先が見つかるまでループ
            // 挿入するため、見ていった要素を一個ずつ後方へズラす。
            while(j >=0 && A[j] > v){
                A[j+1] = A[j];
                j--;
            }
            // 見つけた挿入場所へ挿入。
            A[j+1] = v;
        }
        printArray(A, n);
    }

    // スペース区切りで表示
    public static void printArray(int A[], int n){
        int i;
        for(i=0;i<n-1;i++){
            System.out.print(A[i] + " ");
        }
        System.out.println(A[i]);
    }
}

Main.scala

import scala.io._

object Main extends App {
  val n = StdIn.readInt
  val list = readLine.split(" ").map(_.toInt).toList
  val sortedList = isort(list)
  println(sortedList.mkString(" "))

  // 要素xをリストxsの適当な場所に挿入する。
  def insert(x:Int, xs:List[Int]): List[Int] = {
    xs match{
      case Nil => List(x)
      case y::ys =>
          // リストの先頭よりxが小さいとき
          if(y >= x) x :: xs
          // 先頭に挿入出来ない場合は
          // リストの残りの要素を挿入対象のリストとして再帰
          else y :: insert(x, ys)
    }
  }

  def isort(xs : List[Int]) : List[Int] = {
    println(xs.mkString(" "))
    xs match{
      case Nil => Nil
      // 未挿入リスト => (先頭 :: 残り) => 先頭を挿入, 残りに対して挿入ソートの再帰
      case x :: xs1 =>
        insert(x,  isort(xs1))
    }
  }
}