Sorting

Understanding the common sorting and searching algorithms are quite valuable, as many sorting and searching solutions require tweaks of this. These are recurrent topics in technical interviews, make sure you are aware of how to implement the most common ones: Merge Sort, Quick Sort and Binary Search.

It is worth mentioning the other ones who are also quite common but rarely come in handy or in interview scenarios: Bubble Sort and Selection Sort.

Lastly is good to keep in mind another sorting algorithm which can be extremely efficient, Radix Sort - but this one only works on a finite set of data types like numbers.

Let's have a look at these algorithms and some of their implementations.

Bubble Sort

• Runtime: O(N^2)
• Memory: O(1)

Here we start at the beginning of the list, we grab the first and second elements, if the second is smaller than the first one - we swap them. Then we move on onto the next pair and do the same, continuously until the array is sorted. By doing this the smaller items slowly bubble up to the start of the list, hence the name.

Selection Sort

• Runtime: O(N^2)
• Memory: O(1)

This algorithm is probably the simplest to implement, but extremely inefficient.

Here we find the smallest element in the list by scanning it iteratively, once we find it we move it to the front by swapping with the front element. Then find the second smallest and move it - by doing the same process. We repeat this process until all the elements are sorted.

Merge Sort

• Runtime: O(N log N)
• Memory: Depends
• Recommended reading

Merge Sort divides the array in half, sorts each half and then merges them. Each half will have the same sorting algorithm applied to them. Eventually, the algorithm will just be merging two arrays, the heavy lifting comes in the merge function.

The merge function operates by copying all the elements from the array into a helper array. By doing this we can keep track of where the start of the left and right halves should be (using helperLeft and helperRight). Then, we iterate through the helper array, copying all the elements from each half into the array. In the end, we copy any remaining elements into the target array.

Here is the code in Java:

void mergeSort(int[] array) {
    int[] helper = new int[array.length];
    mergeSort(array, helper, 0, array.length - 1);
}

private void mergeSort(int[] array, int[] helper, int low, int high) {
    if (low < high) {
        int midle = (low + high) / 2;
        mergeSort(array, helper, low, midle); // sort left half
        mergeSort(array, helper, midle + 1, high); // sort right half
        merge(array, helper, low, midle, high); // merge
    }
}

private void merge(int[] array, int[] helper, int low, int middle, int high) {

    // copy onto helper array
    for (int i = low; i <= high; i++) {
        helper[i] = array[i];
    }

    int helperLeft = low;
    int helperRight = middle + 1;
    int current = low;

    /* iterate through the helper array, comparing the left and right half -
    and copying back the smaller element of the two, into the original array
     */
    while (helperLeft <= middle && helperRight <= high) {

        if (helper[helperLeft] <= helper[helperRight]) {
            array[current] = helper[helperLeft];
            helperLeft++;
        } else { // the right element is smaller
            array[current] = helper[helperRight];
            helperRight++;
        }

        current++;
    }

    // copy the rest of the left side of the helper into the original array.
    int remaining = middle - helperLeft;
    for (int i = 0; i <= remaining; i++) {
        array[current + i] = helper[helperLeft + i];
    }
}

The space complexity is 0(n) due to the auxiliary space used to merge parts of the array.

Quick Sort

• Runtime: O(N log N)
• Memory: Log N
• Recommended reading

Here we will pick a random element and partition the array, such that all numbers that are less than the partitioning element come before all the elements that are greater than it. The partitioning is done through a series of swaps.

There can be many ways to do the partition. I find it easier to use the last element as a pivot. The logic is simple, we start from the leftmost element and keep track of the index of smaller (or equal to) elements as i. While traversing, if we find a smaller element, we swap the current element with arr[i]. Otherwise, we ignore the current element.

Here is the code example in Java:

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int partition = partition(arr, low, high);
        quickSort(arr, low, partition-1);
        quickSort(arr, partition+1, high);
    }
}

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 (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i+1;
}

private void swap(int[] array, int left, int right) {
    int temp = array[left];
    array[left] = array[right];
    array[right] = temp;
}

QuickSort vs MergeSort

Quick Sort is preferred over MergeSort for sorting Arrays

Quick Sort in its general form is an in-place sort (i.e. it doesn’t require any extra storage) whereas merge sort requires O(N) extra storage, N denoting the array size which may be quite expensive. Allocating and de-allocating the extra space used for merge sort increases the running time of the algorithm. Comparing average complexity we find that both types of sorts have O(NlogN) average complexity but the constants differ. For arrays, merge sort loses due to the use of extra O(N) storage space.

Most practical implementations of Quick Sort use randomized version. The randomized version has expected time complexity of O(N Log N). The worst case is possible in randomized version also, but the worst-case doesn’t occur for a particular pattern (like sorted array) and randomized Quick Sort works well in practice.

Quick Sort is also a cache-friendly sorting algorithm as it has good locality of reference when used for arrays.

Quick Sort is also tail recursive, therefore tail-call optimizations are done.

Why MergeSort is preferred over QuickSort for Linked Lists?

In case of linked lists, the case is different mainly due to the difference in memory allocation of arrays and linked lists. Unlike arrays, linked list nodes may not be adjacent in memory. Unlike an array, in a linked list, we can insert items in the middle in O(1) extra space and O(1) time. Therefore merge operation of merge sort can be implemented without extra space for linked lists.

In arrays, we can do random access as elements are continuous in memory. Let us say we have an integer (4-byte) array A and let the address of A[0] be x then to access A[i], we can directly access the memory at (x + i*4). Unlike arrays, we can not do random access in a linked list. Quick Sort requires a lot of this kind of access. In linked list to access i’th index, we have to travel every node from the head to i’th node as we don’t have a continuous block of memory. Therefore, the overhead increases for quicksort. Merge sort accesses data sequentially and the need for random access is low.

Radix Sort IRuntime: O(kn)

• Runtime: O(kn) where n is the number of elements and k is the number of passes of the sorting algorithm.
• Recommended Reading

Radix sort is a sorting algorithm for integers (and some other data types) that takes advantage of the fact that integers have a finite number of bits. In radix sort, we iterate through each digit of the number, grouping numbers by each digit. For example, if we have an array of integers, we might first sort by the first digit, so that the Os are grouped together. Then, we sort each of these groupings by the next digit. We repeat this process sorting by each subsequent digit. until finally the whole array is sorted.

Unlike comparison sorting algorithms, which cannot perform better than 0 (N log (N)) in the average case, radix sort has a runtime of O(kn), where n is the number of elements and k is the number of passes of the sorting algorithm.