1. Introduction

QuickSort is a divide-and-conquer sorting algorithm that works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.

2. Program Steps

1. Choose a ‘pivot’ element from the array.

2. Partition the elements into two sub-arrays according to whether they are less than or greater than the pivot.

3. Recursively apply the above steps to the sub-arrays.

4. Combine (concatenate) the sub-arrays and the pivot to get the sorted array.

3. Code Program

public class QuickSort {

    // This function takes last element as pivot, places the pivot element at its correct position
    // in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to the right of pivot.
    public static int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = (low - 1); // index of smaller element

        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to pivot
            if (arr[j] <= pivot) {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    // Main function that sorts arr[low..high] using partition()
    public static void sort(int arr[], int low, int high) {
        if (low < high) {
            // pi is partitioning index, arr[pi] is now at the right place
            int pi = partition(arr, low, high);

            // Recursively sort elements before partition and after partition
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }

    // Driver method
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};

        // Call sort method to sort the array
        sort(arr, 0, arr.length - 1);

        // Print the sorted array
        System.out.println("Sorted array:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output:

Sorted array:
1 5 7 8 9 10

4. Step By Step Explanation

1. The partition function is the heart of the QuickSort algorithm. It selects the last element as the pivot, then places all smaller elements to the left and all larger elements to the right.

2. Within the partition function, the algorithm iterates over the elements, comparing them to the pivot, and swapping as necessary to ensure all elements less than the pivot come before all elements greater than the pivot.

3. The pivot's final position (returned by the partition function) is its sorted position in the array.

4. The sort function then recursively applies the QuickSort logic to the elements before and after the pivot.

5. In the main method, an unsorted array is initialized, the sort method is called to sort the array, and then the sorted array is printed.

The QuickSort algorithm is often faster in practice than other O(n log n) algorithms like Merge Sort or Heap Sort. However, its worst-case time complexity is O(n^2), which can occur when the array is already sorted, and the last element is always chosen as the pivot. There are variations of QuickSort that pick a random element as the pivot or use a median-of-three strategy to mitigate these worst-case scenarios.