Sorting algorithms are categorized into internal and external types. Internal sorting processes data entirely in memory, while external sorting handles datasets too large for memory, requiring access to external storage. This guide focuses on internal sorting algorithms.

For large datasets (n), algorithms with O(n log n) time complexity, such as quicksort, heapsort, and mergesort, are preferred. Quicksort is often considered the most efficient comparison-based method for randomly distributed keys due to its average speed.

Insertion Sort

Insertion sort builds a sorted sequence incrementally by scanning unsorted elements and inserting each into its correct position in the sorted section.

Procedure:

1. Treat the first element as a sorted sequence.
2. Iterate through unsorted elements, inserting each into the sorted sequence by shifting larger elements right.

Implementation:

class InsertionSorter {
    static void sortArray(int[] data) {
        for (int idx = 1; idx < data.length; idx++) {
            int current = data[idx];
            int position = idx - 1;
            while (position >= 0 && data[position] > current) {
                data[position + 1] = data[position];
                position--;
            }
            data[position + 1] = current;
        }
    }
}

Shell Sort

Shell sort improves insertion sort by sorting elements spaced apart by a gap, gradually reducing the gap to one.

Procedure:

1. Choose a gap sequence decreasing to 1.
2. Perform insertion sort on elements at each gap interval.
3. Repeat with smaller gaps until the gap is 1.

Implementation:

class ShellSorter {
    static void sortArray(int[] data) {
        for (int gap = data.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < data.length; i++) {
                int temp = data[i];
                int j;
                for (j = i; j >= gap && data[j - gap] > temp; j -= gap) {
                    data[j] = data[j - gap];
                }
                data[j] = temp;
            }
        }
    }
}

Selection Sort

Selection sort repeatedly selects the smallest element from the unsorted portion and swaps it with the first unsorted element.

Procedure:

1. Find the minimum element in the unsorted array.
2. Swap it with the first unsorted element.
3. Repeat for the remaining unsorted portion.

Implementation:

class SelectionSorter {
    static void sortArray(int[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < data.length; j++) {
                if (data[j] < data[minIndex]) {
                    minIndex = j;
                }
            }
            int swap = data[i];
            data[i] = data[minIndex];
            data[minIndex] = swap;
        }
    }
}

Bubble Sort

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Procedure:

1. Compare adjacent elements, swapping if the first is greater than the second.
2. Repeat for each pair, moving the largest element to the end.
3. Continue for reduced subarrays until no swaps are needed.

Implementation:

class BubbleSorter {
    static void sortArray(int[] data) {
        boolean swapped;
        for (int i = 0; i < data.length - 1; i++) {
            swapped = false;
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j] > data[j + 1]) {
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
}

Merge Sort

Merge sort uses a divide-and-conquer strategy to split the array into halves, recursively sort them, and merge the sorted halves.

Procedure:

1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the two sorted halves into a single sorted array.

Implementation:

class MergeSorter {
    static void sortArray(int[] data, int left, int right, int[] workspace) {
        if (left < right) {
            int mid = (left + right) / 2;
            sortArray(data, left, mid, workspace);
            sortArray(data, mid + 1, right, workspace);
            mergeHalves(data, left, mid, right, workspace);
        }
    }
    
    static void mergeHalves(int[] data, int left, int mid, int right, int[] workspace) {
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (data[i] <= data[j]) {
                workspace[k++] = data[i++];
            } else {
                workspace[k++] = data[j++];
            }
        }
        while (i <= mid) workspace[k++] = data[i++];
        while (j <= right) workspace[k++] = data[j++];
        System.arraycopy(workspace, 0, data, left, k);
    }
}

Quick Sort

Quicksort selects a pivot, partitions the array into elements less than and greater than the pivot, and recursively sorts the partitions.

Procedure:

1. Choose a pivot element.
2. Partition the array so elements less than pivot are on the left, and greater on the right.
3. Recursively apply to left and right partitions.

Implementation:

class QuickSorter {
    static void sortArray(int[] data, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(data, low, high);
            sortArray(data, low, pivotIndex - 1);
            sortArray(data, pivotIndex + 1, high);
        }
    }
    
    static int partition(int[] data, int low, int high) {
        int pivot = data[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (data[j] <= pivot) {
                i++;
                int temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
        int temp = data[i + 1];
        data[i + 1] = data[high];
        data[high] = temp;
        return i + 1;
    }
}