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 \2ドルn\$ 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.

• Caridorc: Binary search works only on sorted arrays, but the array is not sorted... rigth?
• Emily L.: @Caridorc The insertion is always into the sorted part of the array. After x iterations of insertion sort, the x first elements are always sorted. Which means you can use binary search within those x elements to find the next insertion point.
• Caridorc: Clever! +1 padpadpad

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.