Insertion sort in Java

Question

I've written a stable implementation of insertion sort, that sorts an array in ascending order.

Please let me know of any improvements/optimisations that can be made.

import java.util.List;

public class InsertionSort {
    public static void start(List<Integer> arrayToSort){
        for(int i = arrayToSort.size() - 1; i > 0; i--){    // i is the leftmost index of sorted elements
            // j is the index at which the new element inserted in the sorted part of the array
            for(int j = arrayToSort.size() - 1; j >= i; j--){
                if(arrayToSort.get(i - 1) > arrayToSort.get(j)){
                    insert(i - 1, j + 1, arrayToSort);
                    break;
                }
            }
        }
    }

    private static void insert(int source, int destination, List<Integer> arrayToSort){
        arrayToSort.add(destination, arrayToSort.get(source));
        arrayToSort.remove(source);
    }
}

Answer 1

Unnecessary work

Consider a list of \$n\$ elements, then insert(1,0) will move approximately \$2n\$ elements in the array when all it really had to do was swap the two elements.

Note that an optimised insert(source, destination) only needs to move source - destination elements. As this looks like self-learning or possibly homework, I'll leave the details to you.

Use binary search

You can binary search for the insertion point to improve the performance even further.

Answer 2

I guess, it's fine, just a few notes:

public static void start(List<Integer> arrayToSort){

• There should be a space before "{".
• By using List<Integer> you're losing memory and speed when compared to int[]
• If you work with objects, you can make it more general
• This method starts neither this array, nor anything else.
• It should be called sort

---

 private static void insert(int source, int destination, List<Integer> arrayToSort){

I'd call it insertAndRemove or simply move as this is what it does. I'd also call the argument just array as this method doesn't care what it's meant for.