The insertion sort algorithm relies on a simple flow. It starts from the second element and compares it with the element before. If the element before is greater than the current element, then the algorithm swaps the elements. This process continues until the element before is smaller than the current element.

In that case, the algorithm passes to the next element in the array and repeats the flow, as in the following diagram:

The time complexity cases are as follows: best case O(n), average case O(n²), worst case O(n²)

The space complexity case is as follows: worst case O(1)

Based on this flow, an implementation for primitive types will be as follows:

public static void insertionSort(int arr[]) {

  int n = arr.length;

  for (int i = 1; i < n; ++i) {

    int key = arr[i];
    int j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }

    arr[j + 1] = key;
  }
}

For comparing an array of Melon, we need to bring a Comparator in to the implementation as follows:

public static <T> void insertionSortWithComparator(
  T arr[], Comparator<? super T> c) {

  int n = arr.length;

  for (int i = 1; i < n; ++i) {

    T key = arr[i];
    int j = i - 1;

    while (j >= 0 && c.compare(arr[j], key) > 0) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }

    arr[j + 1] = key;
  }
}

Here, we have a Comparator that sorts the melons by type and weight written in Java 8 functional style using the thenComparing() method:

Comparator<Melon> byType = Comparator.comparing(Melon::getType)
  .thenComparing(Melon::getWeight);

Having an array of Melon, the preceding Comparator, and the insertionSortWithComparator() method in a utility class named ArraySorts, we can write something as follows:

Melon[] melons = {...};
ArraySorts.insertionSortWithComparator(melons, byType);