Sorting Algorithms: Slowest to Fastest

Imagine trying to find a word in a dictionary that isn’t in alphabetical order.

You’d have to scan every page, which would take a huge amount of effort and time. Enter sorting algorithms. These algorithms are designed to scan data and sort items quickly, which tremendously helps us search for them. 

There are various ways in which we can sort items. Let’s examine each of them along with their time and space complexities.

Bubble Sort

This is the simplest sorting algorithm. We’ll compare each adjacent pair and check if the elements are in order. If they aren’t, we swap both elements. We keep doing this until all elements are sorted.

for(int i = 0;i < n; i++){
    for(int j=0;j < n - 1; j++){
        if(arr[j] > arr[j+1]){
            int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
       }
    }
}

Performance Analysis

Time Complexity

1. Worst case: O(n²). Since we loop through n elements n times, n being the length of the array, the time complexity of bubble sort becomes O(n²).
2. Best case: O(n²). Even if the array is sorted, the algorithm checks each adjacent pair and hence the best-case time complexity will be the same as the worst-case.

Space Complexity: O(1)

Since we aren’t using any extra data structures apart from the input array, the space complexity will be O(1).

Try This: Tackling Jump Game Problems on LeetCode 

Revised Bubble Sort

In the above sorting algorithm, we find that even if our array is already sorted, the time complexity will be the same, i.e. O(n²).

We’ll come up with a revised algorithm to overcome this. To identify if the array has been sorted, we’ll create a flag that will check if a swap has occurred between any adjacent pairs. If there is no swap while traversing the entire array, we know that the array is completely sorted and we can break out of the loop. This considerably reduces the time complexity of the algorithm.

for(int i = 0;i < n; i++){
    boolean isSwapped = false;
    for(int j=0;j < n - 1; j++){
       if(arr[j] > arr[j+1]){
            int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
            isSwapped = true;
        }
    if(!isSwapped){
        break;  
     }
   }
}

Performance Analysis

Time Complexity

1. Worst case: O(n²). Similar to bubble sort.
2. Best case: O(n). In this algorithm, we break our loop if our array is already sorted. So, the best-case time complexity will become O(n).

Space Complexity: O(1).

Selection Sort

In this sorting algorithm, we assume that the first element is the minimum element. Then we check to see if an element lower than the assumed minimum is present in the rest of the array. If there is, we swap the assumed minimum and the actual minimum. Otherwise, we move on to the next element.

for(int i=0;i<arr.length; i++) {
   int minIndex = i;  
   for(int j=i+1;j<arr.length; j++) {
      if(arr[j]<arr[minIndex]) {
        minIndex = j;
      }
   }
   int temp = arr[i];
   arr[i] = arr[minIndex];
   arr[minIndex] = temp;
}

Performance Analysis

Time Complexity

1. Worst case: O(n²). Since we traverse through the remaining array to find the minimum for each element, the time complexity will become O(n²).
2. Best case: O(n²). Even if the array has already been sorted, our algorithm looks for the minimum in the rest of the array. As a result, the best-case time complexity is the same as the worst-case.

Space Complexity: O(1)

Similar to the previous algorithms, we aren’t making use of any extra data structure apart from the input array so, the space complexity will be O(1).

More on Software Engineering: Sliding Window Algorithm Explained

Insertion Sort

In this sorting algorithm, we check to see if the order is correct for each element until we reach the current element. Since the first element is in order, we start from the second element and check if the order is maintained. If not, then we swap them. So, on any given element, we check if the current element is greater than the previous element. If it’s not, we keep swapping elements until our current element is greater than the previous element.

for(int i = 1;i < n; i++) {
    int j = i;
    while(j > 0 && arr[j] < arr[j-1]) {
        int temp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = temp;
        j--;
    }
}

Performance Analysis

Time Complexity

1. Worst case: O(n²). In a worst case situation, our array is sorted in descending order. So, for each element, we have to keep traversing and swapping elements to the left.
2. Best case: O(n). In the best case, our array is already sorted. So for each element, we compare our current element to the element at the left only once. Since the order is correct, we don’t swap and move on to the next element. Hence the time complexity will be O(n).

Space Complexity: O(1)

Since we are not making use of any extra data structure apart from the input array, the space complexity will be O(1).

Quick Sort

Quick sort is also known as a “partition sort.” This sorting algorithm is faster than the previous algorithms because this algorithm uses the concept of divide and conquer.

First, we decide on a pivot element. We then find the correct index for this pivot position and divide the array into two subarrays. One subarray will contain elements that are lesser than our pivot, and the other subarray will contain elements that are greater than our pivot. We then recursively call these two sub-arrays, and the process goes on until we can’t further divide the array.

public static void quicksort(int[] arr, int low, int high) {
    if(low >= high) return;
    int pivotPosition = partition(arr, low, high);
    quicksort(arr,low, pivotPosition-1);
    quicksort(arr, pivotPosition+1, high);
}

But how do we divide the sub-array?

We assume the last element of our array to be our pivot. We then traverse the entire array using the two-pointer technique. The elements encountered by the left pointer should be lower than the pivot and elements encountered by the right pointer should be greater than pivot. If not, we swap the elements at the left and right pointers so that for a particular position in the array, the elements to the left are lower while higher at the right. We then insert our pivot at this position.

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int left = low, right = high-1;
    while(left < right) {
       while(arr[left]<pivot) {
            left++;
       }
       while(arr[right]>pivot) {
            right--; 
       }
       if(left >= right) {
            break;
       }
       int temp = arr[left];
       arr[left] = arr[right];
       arr[right] = temp;
    }
    int temp = arr[left];
    arr[left] = arr[high];
    arr[high] = temp;
    return left;
}

Performance Analysis

Time Complexity

1. Worst-case: O(n²). When the array is sorted in descending order or all the elements are the same in the array, the time complexity jumps to O(n²), since the sub-arrays are highly unbalanced.
2. Best-case: O(nlogn). First, we’ll divide the array into two sub-arrays recursively, which will cost a time complexity of O(logn). For each function call, we are calling the partition function, which costs O(n) time complexity. Hence the total time complexity is O(nlogn).

Space Complexity: O(n)

Since we are recursively calling the quicksort function, an internal stack is used to store these function calls. There will be, at most, n calls in the stack, and hence the space complexity will be O(n).

Merge Sort

Like quick sort, merge sort also uses the divide and conquer technique. Except in merge sort, most of the work is done during the merging of the sub-arrays. In quick sort, the majority of work is done during the partitioning/dividing of the array. This is why quick sort is also known as a partition sort.

The below function will recursively break the array into two sub-arrays until each sub-array has only one element.

public void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r-l)/2;
        sort(arr, l, m);
        sort(arr , m+1, r);
        merge(arr, l, m, r);
    }
}

After that, we store these sub-arrays in two new arrays. Now, we can start merging them based on their order, and store them into our input array. After all these subarrays are merged, our input array will be sorted.

public void merge(int arr[], int l, int m, int r) {
    int n1 = m-l+1;
    int n2 = r-m;
    int[] L = new int[n1];
    int[] R = new int[n2];
    for(int i = 0;i < n1; i++) {
        L[i] = arr[l+i];
    }
    for(int i = 0;i < n2; i++) {
        R[i] = arr[m+1+i];
    }
    int i = 0, j = 0, k =l;
    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) {
            arr[k++] = L[i++];
        }
        else {
            arr[k++] = R[j++];
        }
    }
    while(i < n1) {
        arr[k++] = L[i++];
    }
    while(j < n2) {
        arr[k++] = R[j++];
    }
}

Performance Analysis

Time Complexity

1. Worst case: O(nlogn). The worst-case time complexity is the same as the best case.
2. Best case: O(nlogn). We are dividing the array into two sub-arrays recursively, which will cost a time complexity of O(logn). For each function call, we are calling the partition function, which costs O(n) time complexity. Hence the total time complexity is O(nlogn).

Space Complexity: O(n)

Since we are recursively calling the MergeSort function, an internal stack is used to store these function calls. There will be at most n calls in the stack, and hence, the space complexity will be O(n).

More on Software Engineering: How to Use Pass, Continue and Break in Python

Advantages of Each Sorting Algorithm

Since we sort the elements after comparing them with each other, each of the above algorithms are all comparison-based. However, there are other non-comparison-based sorting algorithms, such as counting sort, radix sort, bucket sort, etc. These are also called linear sorting algorithms because their time complexity is O(n).

Finally, each algorithm has their own pros and cons, and their implementation depends on your priority. If efficiency is not an issue, we can use bubble sort because it’s easy to implement. Or we can use insertion sort when the array is nearly sorted, since the time complexity is linear.