Heap sort is an algorithm that relies on a binary heap (complete binary tree).

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

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

At the first step, the algorithm uses the array provided to build this heap and transform it into a Max Heap (the heap is represented by another array). Since this is a Max Heap, the largest element is the root of the heap. At the next step, the root is swapped with the last element from the heap and the heap size is reduced by 1 (delete the last node from the heap). The elements that are at the top of the heap come out in sorted order. The final step consists of heapify (the recursive process that builds the heap in a top-down manner), and the root of the heap (reconstruct the Max Heap). These three steps are repeated until the heap size is greater than 1:

For example, let's assume the array from the preceding diagram – 4, 5, 2, 7, 1:

1. So, at the first step, we build the heap: 4, 5, 2, 7, 1.
2. We build the Max Heap: 7, 5, 2, 4, 1 (we swapped 5 with 4, 4 with 7, and 5 with 7).
3. Next, we swap the root (7) with the last element (1) and delete 7. Result: 1, 5, 2, 4, 7.
4. Further, we construct the Max Heap again: 5, 4, 2, 1 (we swapped 5 with 1 and 1 with 4).
5. We swap the root (5) with the last element (1) and delete 5. Result: 1, 4, 2, 5, 7.
6. Next, we construct the Max Heap again: 4, 1, 2 (we swapped 1 with 4).
7. We swap the root (4) with the last element (2) and delete 4. Result: 2, 1.
8. This is a Max Heap, so swap the root (2) with the last element (1) and remove 2: 1, 2, 4, 5, 7.
9. Done! There is a single element left in the heap (1).

In code lines, the preceding example can be generalized as follows:

public static void heapSort(int[] arr) {
  int n = arr.length;

  buildHeap(arr, n);

  while (n > 1) {
    swap(arr, 0, n - 1);
    n--;
    heapify(arr, n, 0);
  }
}

private static void buildHeap(int[] arr, int n) {
  for (int i = arr.length / 2; i >= 0; i--) {
    heapify(arr, n, i);
  }
}

private static void heapify(int[] arr, int n, int i) {
  int left = i * 2 + 1;
  int right = i * 2 + 2;
  int greater;

  if (left < n && arr[left] > arr[i]) {
    greater = left;
  } else {
    greater = i;
  }

  if (right < n && arr[right] > arr[greater]) {
    greater = right;
  }

  if (greater != i) {
    swap(arr, i, greater);
    heapify(arr, n, greater);
  }
}

private static void swap(int[] arr, int x, int y) {
  int temp = arr[x];
  arr[x] = arr[y];
  arr[y] = temp;
}

If we want to compare objects, then we have to bring a Comparator into the implementation. This solution is available in the code bundled to this book under the name heapSortWithComparator().

Here, it is a Comparator written in Java 8 functional style that uses the thenComparing() and reversed() methods to sort the melons in descending order by type and weight:

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

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

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

We will stop our dissertation regarding sorting arrays here, but, in the code bundled to this book, there are a few more sorting algorithms available:

There are many other algorithms dedicated to sorting arrays. Some of them are built on top of those presented here (for example, Comb sort, Cocktail sort, and Odd-even sort are flavors of Bubble sort, Bucket sort is a distribution sort commonly relying on Insertion sort, Radix sort (LSD) is a stable distribution similar to Bucket sort, and Gnome sort is a variation of Insertion sort).

Others are different approaches (for example, Quicksort implemented by the Arrays.sort() method, and Merge sort implemented by Arrays.parallelSort()).

By way of a bonus to this section, let's see how we can shuffle an array. An efficient way to accomplish this relies on the Fisher-Yates shuffle (known as the Knuth shuffle). Basically, we loop the array in reverse order and we randomly swap elements. For primitives (for example, int), the implementation is as follows:

public static void shuffleInt(int[] arr) {

  int index;

  Random random = new Random();

  for (int i = arr.length - 1; i > 0; i--) {

    index = random.nextInt(i + 1);
    swap(arr, index, i);
  }
}

In the code bundled to this book, there is also the implementation for shuffling an array of Object.