Java Example 3

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// Kaizer here. I implemented and compared different sorting algorithms using 3 main ones. quicksort, mergesort, and heapsort, in terms of performance.
public class SortingComparison {
    // function to print an array
    public static void printArray(List<Integer> arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // quicksort implementation
    public static int partition(List<Integer> arr, int low, int high) {
        int pivot = arr.get(high);
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr.get(j) < pivot) {
                i++;
                Collections.swap(arr, i, j);
            }
        }
        Collections.swap(arr, i + 1, high);
        return i + 1;
    }

    public static void quicksort(List<Integer> arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quicksort(arr, low, pi - 1);
            quicksort(arr, pi + 1, high);
        }
    }

    // mergesort implementation
    public static void merge(List<Integer> arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        List<Integer> L = new ArrayList<>(n1);
        List<Integer> R = new ArrayList<>(n2);

        for (int i = 0; i < n1; i++)
            L.add(arr.get(left + i));
        for (int j = 0; j < n2; j++)
            R.add(arr.get(mid + 1 + j));

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L.get(i) <= R.get(j)) {
                arr.set(k, L.get(i));
                i++;
            } else {
                arr.set(k, R.get(j));
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr.set(k, L.get(i));
            i++;
            k++;
        }

        while (j < n2) {
            arr.set(k, R.get(j));
            j++;
            k++;
        }
    }

    public static void mergesort(List<Integer> arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergesort(arr, left, mid);
            mergesort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    // heapsort implementation
    public static void heapify(List<Integer> arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr.get(left) > arr.get(largest))
            largest = left;

        if (right < n && arr.get(right) > arr.get(largest))
            largest = right;

        if (largest != i) {
            Collections.swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    public static void heapsort(List<Integer> arr) {
        int n = arr.size();
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        for (int i = n - 1; i > 0; i--) {
            Collections.swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    // function to measure and compare sorting times
    public static void compareSorts(List<Integer> arr) {
        List<Integer> arr1 = new ArrayList<>(arr);
        List<Integer> arr2 = new ArrayList<>(arr);
        List<Integer> arr3 = new ArrayList<>(arr);

        long start = System.nanoTime();
        quicksort(arr1, 0, arr1.size() - 1);
        long end = System.nanoTime();
        double quicksortTime = (end - start) / 1e9;
        System.out.println("Quicksort time: " + quicksortTime + " seconds");

        start = System.nanoTime();
        mergesort(arr2, 0, arr2.size() - 1);
        end = System.nanoTime();
        double mergesortTime = (end - start) / 1e9;
        System.out.println("Mergesort time: " + mergesortTime + " seconds");

        start = System.nanoTime();
        heapsort(arr3);
        end = System.nanoTime();
        double heapsortTime = (end - start) / 1e9;
        System.out.println("Heapsort time: " + heapsortTime + " seconds");
    }

    public static void main(String[] args) {
        List<Integer> arr = new ArrayList<>(List.of(12, 11, 13, 5, 6, 7));
        System.out.print("Original array: ");
        printArray(arr);

        compareSorts(arr);
    }
}