Sorting

Generic merge

The generic merge algorithm is used to sort two ordered lists.

public static <E extends Comparable<E>> E[] genericMerge(E[] a, E[] b){
        E[] result = (E[])new Comparable[a.length + b.length];
        int ri = 0, ai = 0, bi = 0;
        // While both lists contain items
        while(!(ai == a.length || bi == b.length)){
            // Compare the current items
            if(a[ai].compareTo(b[bi]) > 0){
                // Add b to the result
                result[ri++] = b[bi++];
            } else{
                // Add a to the result
                result[ri++] = a[ai++];
            }
        }
        // Add the remainder of a
        while(ai < a.length){
            result[ri++] = a[ai++];
        }
        // Add the remainder of b
        while(bi < b.length){
            result[ri++] = b[bi++];
        }
        // Return the result
        return result;
    }

Merge sort

Merge sort is a divide and conquer sorting algorithm. It takes the list, recursively splits it until left with singletons and then uses the generic merge algorithm above to merge the sorted lists.

private static <E> E[] mergeSort(E[] list){
    int size = list.length;
    if(size <= 1){
        // Return singleton or empty list for merging
        return list;
    } else{
        // Find middle index
        int pivot = Math.floorDiv(size, 2);
        // Create lists for two halves
        Object[] left = new Object[pivot];
        Object[] right = new Object[size-pivot];
        // Copy list to halves
        System.arraycopy(list, 0, left, 0, pivot);
        System.arraycopy(list, pivot, right, 0, size-pivot);

        // Recursively merge sort halves
        left = mergeSort((E[])left);
        right = mergeSort((E[])right);
        // Return merged sorted lists
        return genericMerge((E[])left, (E[])right);

    }
}

Merge sort has time complexity $O(n\log n)$.

Quick sort

Quick sort is a randomised divide and conquer sorting algorithm. It chooses a random pivot, then splits the list into items smaller and larger than the pivot, then does the same for each of those lists until every item has been a pivot. The worst case of quick sort occurs when the random pivot is not ideal every time which has complexity $O(n^2)$. The average case is $O(n\log n)$.

Selection sort

Selection sort can be implemented using an unsorted priority queue. It needs $n$ insertions and $O(n^2)$ removeMin calls, giving an overall run time of $O(n^2)$.

Insertion sort

Insertion sort uses a sorted priority queue. It still has $O(n^2)$ run time but may perform better than selection sort.