1. Selection Sort

The algorithm divides the input list into two parts: a sorted sublist built up from left to right, and the remaining unsorted items. During each iteration, the smallest element from the unsorted section is identified and swapped into its correct position at the end of the sorted sublist.

• Time Complexity: O(N^2) where N is the array length.
• Space Complexity: O(1) using only a few temporary variables.

public class ArraySorter {
    public int[] sort(int[] data) {
        int size = data.length;
        for (int curr = 0; curr < size - 1; curr++) {
            int smallestIdx = curr;
            for (int next = curr + 1; next < size; next++) {
                if (data[next] < data[smallestIdx]) {
                    smallestIdx = next;
                }
            }
            exchange(data, curr, smallestIdx);
        }
        return data;
    }

    private void exchange(int[] data, int a, int b) {
        int tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }
}

2. Insertion Sort

This stable sorting algorithm builds the final sorted array one item at a time. It is particularly efficient for datasets that are already substantially sorted.

public class ArraySorter {
    public int[] sort(int[] data) {
        int length = data.length;
        for (int i = 1; i < length; i++) {
            int key = data[i];
            int shiftIdx = i;
            while (shiftIdx > 0 && data[shiftIdx - 1] > key) {
                data[shiftIdx] = data[shiftIdx - 1];
                shiftIdx--;
            }
            data[shiftIdx] = key;
        }
        return data;
    }
}

3. Merge Sort

A divide-and-conquer algorithm that splits the array into halves, recursively sorts them, and finally merges the sorted halves back together.

public class MergeArraySorter {
    private int[] aux;

    public int[] sort(int[] data) {
        aux = new int[data.length];
        divideAndMerge(data, 0, data.length - 1);
        return data;
    }

    private void divideAndMerge(int[] data, int start, int end) {
        if (start >= end) {
            return;
        }
        int center = start + (end - start) / 2;
        divideAndMerge(data, start, center);
        divideAndMerge(data, center + 1, end);
        combine(data, start, center, end);
    }

    private void combine(int[] data, int start, int center, int end) {
        int left = start, right = center + 1, k = 0;
        while (left <= center && right <= end) {
            if (data[left] <= data[right]) {
                aux[k++] = data[left++];
            } else {
                aux[k++] = data[right++];
            }
        }
        while (left <= center) {
            aux[k++] = data[left++];
        }
        while (right <= end) {
            aux[k++] = data[right++];
        }
        for (int p = 0; p < end - start + 1; p++) {
            data[start + p] = aux[p];
        }
    }
}

4. Heap Sort

Heap sort optimizes selection sort by using a max-heap data structure to efficiently find the maximum element in O(log N) time instead of O(N). The parent of node i is (i-1)/2, the left child is (2*i)+1, and the right child is (2*i)+2.

• Time Complexity: O(N log N) where N is the array length.
• Space Complexity: O(1).

public class HeapArraySorter {
    public int[] sort(int[] data) {
        int lastIdx = data.length - 1;
        constructMaxHeap(data, lastIdx);
        for (int i = lastIdx; i > 0; i--) {
            exchange(data, 0, i);
            sink(data, 0, i - 1);
        }
        return data;
    }

    private void constructMaxHeap(int[] data, int lastIdx) {
        for (int node = (lastIdx - 1) / 2; node >= 0; node--) {
            sink(data, node, lastIdx);
        }
    }

    private void sink(int[] data, int node, int limit) {
        int leftChild = node * 2 + 1;
        if (leftChild > limit) return;
        int rightChild = leftChild + 1;
        int largest = node;
        if (leftChild <= limit && data[leftChild] > data[largest]) {
            largest = leftChild;
        }
        if (rightChild <= limit && data[rightChild] > data[largest]) {
            largest = rightChild;
        }
        if (largest != node) {
            exchange(data, node, largest);
            sink(data, largest, limit);
        }
    }

    private void exchange(int[] data, int a, int b) {
        int tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }
}

5. Quick Sort

Quick sort selects a 'pivot' element and partitions the array around it, placing the pivot in its final sorted position. It then recursively sorts the sub-arrays on either side. Randomization is utilized to avoid the worst-case O(N^2) scenario on already sorted inputs.

• Time Complexity: O(N log N) on average; O(N^2) in the worst case.
• Space Complexity: O(log N) for the recursion stack.

public class QuickArraySorter {
    public int[] sort(int[] data) {
        quickSort(data, 0, data.length - 1);
        return data;
    }

    private void quickSort(int[] data, int low, int high) {
        if (low >= high) return;
        int pivotIdx = randomPartition(data, low, high);
        quickSort(data, low, pivotIdx - 1);
        quickSort(data, pivotIdx + 1, high);
    }

    private int randomPartition(int[] data, int low, int high) {
        exchange(data, high, new Random().nextInt(high - low + 1) + low);
        int boundary = low;
        for (int curr = low; curr < high; curr++) {
            if (data[curr] <= data[high]) {
                exchange(data, boundary, curr);
                boundary++;
            }
        }
        exchange(data, boundary, high);
        return boundary;
    }

    private void exchange(int[] data, int a, int b) {
        int tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }
}

Hoare Partition Optimization

Using collision pointers (Hoare partition scheme) can accelerate the partitioning process by moving both ends towards the center simultaneously.

public class HoareQuickSorter {
    public int[] sort(int[] data) {
        quickSort(data, 0, data.length - 1);
        return data;
    }

    private void quickSort(int[] data, int low, int high) {
        if (low >= high) return;
        int pivotIdx = hoarePartition(data, low, high);
        quickSort(data, low, pivotIdx - 1);
        quickSort(data, pivotIdx + 1, high);
    }

    private int hoarePartition(int[] data, int low, int high) {
        exchange(data, high, new Random().nextInt(high - low + 1) + low);
        int leftPtr = low, rightPtr = high - 1;
        while (leftPtr <= rightPtr) {
            while (leftPtr < high && data[leftPtr] < data[high]) leftPtr++;
            while (rightPtr >= low && data[rightPtr] > data[high]) rightPtr--;
            if (leftPtr >= rightPtr) break;
            exchange(data, leftPtr, rightPtr);
            leftPtr++;
            rightPtr--;
        }
        exchange(data, leftPtr, high);
        return leftPtr;
    }

    private void exchange(int[] data, int a, int b) {
        int tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }
}