ノームソートを紹介します。

ノームソートは隣接する2つの要素を比較し、順序が正しければ次の要素へ、順序が逆であれば2つを入れ替えて前の要素へ移動する。という単純なアルゴリズムです。

sort/GnomeSort.java

package sort;

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class GnomeSort {

 public static void swap(List list, int index1, int index2) { 
   E t = list.get(index1); list.set(index1, list.get(index2)); list.set(index2, t);
 } 

 public static > void sort(List list) {
   int i = 0;
   while (i < (list.size() - 1)) {
     if (list.get(i).compareTo(list.get(i + 1)) > 0) {
　　　   swap(list, i, i + 1);
　　　   if (i != 0) {
   　　　   i--;
 　　    }
     } else {
　　　　 i++;
     }
   }
 }

}