Sorting Algorithms Summary

Bubble sort, insertion sort, selection sort, quick sort, heap sort, merge sort, counting sort, bucket sort and radix sort.

Table of Contents
· Comparison-Based Sorting Algorithms
· Non Comparison-Based Sorting Algorithms
· Time and Space Complexity
· Stability
  ∘ Why Selection sort is not stable?
  ∘ Why Quick sort is not stable?
  ∘ Why Heap sort is not stable?

Comparison-Based Sorting Algorithms

• Bubble sort algorithm
• Insertion sort algorithm
• Selection sort algorithm
• Quick sort algorithm
• Heap sort algorithm
• Merge sort algorithm

comparison-based sorting algorithms

Non Comparison-Based Sorting Algorithms

• Counting sort algorithm
• Bucket sort algorithm
• Radix sort algorithm

non comparison-based sorting algorithms

Time and Space Complexity

time and space complexity

Stability

Equal elements have the same order in the input and output if a sorting algorithm is stable.

In below demos, a and b are used to denoted the order of value 2.

Why Selection sort is not stable?

Selection sort works by selecting the smallest element and swapping it with the first element in the unsorted subarray. At the first round, we find the 1 is the least element and swap it with 2a. That way, the relative order of 2a and 2b is changed.

unstable selection sort

Why Quick sort is not stable?

Quick sort is not stable because it may rearrange equal elements/keys. Supposed that we pick 2a as pivot, values less than or equal to the pivot are moved to the left subarray. The equal element, 2b, is rearranged to the left of 2a. Thus, the original order of 2a and 2b is not preserved.

unstable quick sort

Why Heap sort is not stable?

When heap sort sorts elements in ascending order, it swaps the largest element at root with the last element in the the heap. In below example, 2a is picked first and put into the back of sorted array. Therefore, we get 2b before 2a in the sorted output.