package Sort;

import java.util.Arrays;

public class InsertionSort {

    public static int[] sort(int[] list) {

        for (int i = 1; i < list.length; i++) {

            int x = list[i]; // 哨兵

            int j = i;

            while (j > 0 && x < list[j - 1]) {

                list[j] = list[j - 1];

                j--;

            }

            list[j] = x;

        }

        return list;

    }

    public static void main(String[] args) {

        int[] list = {5,4,3,2,1,6,8,7};

        System.out.println(Arrays.toString(sort(list)));

    }

}