Abstract


  • Basically re-arranging a collection of items or data elements in an ascending or descending order

In-Place

Stability of Sorting

  • Stable if the items with the same value stay in the same order after sorting
  • Unstable if the items with the same value doesn’t stay in the same after sorting

Divide-and-Conquer Sorting

  • Divide: split array into two halves
  • Recursion up: hit the base case, kickstart sorting the two halves
  • Combine: merge the sorted halves

Identify Sorting Algorithms


Ways to test

  1. Check on the stability
  2. Check on the time complexity
    • Sorted Input (Best-case performance)
    • Random Input (Average-case performance)
    • Reverse Sorted Input (Worst-case performance)
    • Almost Sorted Input (Tests adaptive behaviour)
  3. Number of Comparisons & Swaps (Helps distinguish algorithms like Merge Sort from Quick Sort)

Time complexity

AlgorithmBest CaseWorst CaseStabilityNotes
Bubble sortO(n)O(n^2)Slow, worst on random & reverse-sorted
Selection sortO(n^2)O(n^2)Similar time across all cases - slow
Insertion sortO(n)O(n^2)Very fast on almost sorted data (minimal swaps)
Merge sortO(nlogn)O(nlogn)Consistent times
Quick sortO(nlogn)O(n^2)Worst on reverse sorted (pivot selection strategy)

Important

Stable & worst case: Merge sort perform significantly better.

Stable & almost sorted: If the array has a small misplaced element at the wrong end, Bubble Sort can still take O(n^2). While other stable sorting algorithms will be significantly faster. Especially insertion sort is the fastest.

Unstable & average case: Quick sort performs significantly better than selection sort. However, if the costs of the two sorting algorithms are not directly comparable and we are unable to construct a worst-case scenario for quick sort due to the unclear pivot selection mechanism in quick sort, we cannot directly compare the cost differences between the average case and the worst case. In this case, we should plot a graph to illustrate how the cost grows as the number of elements increases. Quick sort will grow much slower than selection sort.

Not all the O(n^2) sorting algorithms are the same

Different algorithms have different inputs that they are good or bad on.

For example, Bubble Sort, Selection Sort and Insertion Sort have the time complexity. But on sorted or almost sorted array, bubble sort and insertion sort have the time complexity while selection sort has time complexity.

Number of comparisons

AlgorithmBest CaseWorst CaseNotes
Bubble sortO(n)O(n^2)Less comparisons in best case
Selection sortO(n^2)O(n^2)Always does n^2 comparisons
Insertion sortO(n)O(n^2)Less comparisons in best case
Merge sortO(nlogn)O(nlogn)Consistent and less number of comparisons
Quick sortO(nlogn)O(n^2)Only less number of comparisons in the best case

Number of swaps

AlgorithmBest CaseWorst CaseNotes
Bubble sortO(1)O(n^2)High swaps in worst case
Selection sortO(n)O(n)Always does n swaps
Insertion sortO(1)O(n^2)High swaps in worst case
Merge sortO(nlogn)O(nlogn)High data movement, but stable
Quick sortO(nlogn)O(n^2)Low swaps in best case, worst in worst-case

Minimal swap operation

Selection sort has the least number of swap operations compared to bubble sort and insertion sort in the worst case.

Selection sort has swaps in the worst case, both bubble sort and insertion sort has swap in the worst case.

Bubble Sort


  • The idea here is that at each iteration , we are are going to ‘bubble up’ the biggest element in the range to the position. If no ‘bubbling’ happens in that particular iteration, it means the array is fully sorted and it is safe to terminate the sorting early
  • Bubble sort implementation in Java

Selection Sort


  • The idea here is that at each iteration , we are are going to select the smallest element in the range of the Array. Then swap it with element at the position
  • Selection sort implementation in java

Insertion Sort


  • The idea here is that at each iteration , we are are going to insert the element at the position to the prefix Array that is long, such that the new prefix array which is long remains sorted

Merge Sort


Handle large dataset well

The performance gains on large dataset with time complexity is huge.

And we can perform sorting on subset of the dataset at a time. For example, if our dataset is 10GB, and we need to load the data into the RAM to perform the sorting, but there is only 2GB RAM. With merge sort, we are able to load in 2GB at a time to perform sorting, and eventually sort the dataset.

Quick Sort


  • Divide: Select a ‘pivot’ element from the array
  • Partition: Rearrange the array so that all elements smaller than the pivot are placed to its left and all elements greater than the pivot are placed to its right.
  • Conquer: Recursively apply the same process (steps 1 and 2) to the sub-array on the left of the pivot and the sub-array on the right of the pivot. The base case for recursion occurs when an array or sub-array has one or zero elements, as they are already sorted by default

Important

Quick sort is an In-Place sorting algorithm.

How is partition implemented?

Essentially, we have two indices, i and j, both starting at index . The index i keeps track of the last position where an element smaller than the pivot was placed. Meanwhile, j scans the array from index to the last index.

Here is a short video showing how partition is carried out.

Worst case is n^2

This happens when the pivot selection consistently leads to highly unbalanced partitions, causing the recursion depth to reach O(n)  instead of  O(log n).

Bucket Sort


  1. The algorithm divides the value range of elements into categories called buckets. Each bucket covers a smaller, mutually exclusive range
  2. Elements are placed into the corresponding bucket based on their value
  3. Each bucket is sorted individually, and the elements from all buckets are then combined to form the final sorted array.

Important

When elements are well-distributed across many buckets, bucket sort performs in O(n) because each bucket has a small number of elements, which can be sorted quickly or no sorting is even required!

When elements are clustered into a few buckets, and if the sorting algorithm for those buckets takes more time (e.g., due to a large number of elements in some buckets), the overall complexity can rise to O(n logn).

Leetcode questions

References