Heap Sort

Heap sort operates on a heap data structure. The key steps involve heap construction and sorting.

Heap Construction

Heap construction involves building either a max-heap (for ascending order) or min-heap (for descending order). The process uses a downward adjustment method starting from the last parent node.

Max-Heap Construction Code:

public void buildMaxHeap(int[] data) {
    for (int parent = (data.length - 2) / 2; parent >= 0; parent--) {
        adjustDown(data, parent, data.length);
    }
}

private void adjustDown(int[] data, int parent, int size) {
    int child = parent * 2 + 1;
    while (child < size) {
        if (child + 1 < size && data[child + 1] > data[child]) {
            child++;
        }
        if (data[child] > data[parent]) {
            swap(data, child, parent);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

Sorting

After heap construction, each root element is swapped with the last element, followed by a downward adjustment.

Heap Sort Implementation:

public void heapSort(int[] data) {
    buildMaxHeap(data);
    int end = data.length - 1;
    while (end > 0) {
        swap(data, 0, end);
        adjustDown(data, 0, end);
        end--;
    }
}

Complexity Analysis:

• Time: O(n log n)
• Space: O(1)
• Stability: Unstable

Quick Sort

Quick sort uses a divide-and-conquer approach with partitioning.

Partition Methods

1. Hoare's Partition:

private int hoarePartition(int[] arr, int low, int high) {
    int pivot = arr[low];
    int i = low, j = high;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        while (i < j && arr[i] <= pivot) i++;
        swap(arr, i, j);
    }
    swap(arr, low, j);
    return j;
}

2. Lomuto Partition (Pivot Hole Method):

private int lomutoPartition(int[] arr, int low, int high) {
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) low++;
        arr[high] = arr[low];
    }
    arr[high] = pivot;
    return high;
}

Optimizations

1. Median-of-Three Pivot Selection:

private int medianOfThree(int[] arr, int a, int b, int c) {
    if (arr[a] < arr[b]) {
        return arr[b] < arr[c] ? b : (arr[a] < arr[c] ? c : a);
    } else {
        return arr[a] < arr[c] ? a : (arr[b] < arr[c] ? c : b);
    }
}

2. Insertion Sort for Small Subarrays:

private void insertionSort(int[] arr, int start, int end) {
    for (int i = start + 1; i <= end; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= start && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Non-Recursive Implementasion

public void quickSortIterative(int[] arr) {
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    stack.push(arr.length - 1);
    
    while (!stack.isEmpty()) {
        int high = stack.pop();
        int low = stack.pop();
        int pivot = lomutoPartition(arr, low, high);
        
        if (pivot - 1 > low) {
            stack.push(low);
            stack.push(pivot - 1);
        }
        if (pivot + 1 < high) {
            stack.push(pivot + 1);
            stack.push(high);
        }
    }
}

Complexity Enalysis:

• Time: O(n log n) average, O(n²) worst-case
• Space: O(log n)
• Stability: Unstable

Merge Sort

Merge sort divides the array into halves, recursively sorts them, and merges the sorted halves.

Recursive Implementation

public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    System.arraycopy(temp, 0, arr, left, temp.length);
}

Non-Recursive Implementation

public void mergeSortIterative(int[] arr) {
    for (int gap = 1; gap < arr.length; gap *= 2) {
        for (int i = 0; i < arr.length; i += 2 * gap) {
            int left = i;
            int mid = Math.min(i + gap - 1, arr.length - 1);
            int right = Math.min(i + 2 * gap - 1, arr.length - 1);
            merge(arr, left, mid, right);
        }
    }
}

Complexity Analysis:

• Time: O(n log n)
• Space: O(n)
• Stability: Stable

External Merge Sort

For large datasets that don't fit in memory:

1. Split the data into mangaeable chunks
2. Sort each chunk individually
3. Merge the sorted chunks using k-way merge