TeachingBee

Understanding Different Types of Sorting Algorithms

Types of sorting

Introduction

Different types of sorting techniques are fundamental concepts in computer science that arrange data into a particular order, such as numerical order or lexicographic order. Efficient sorting is critical for optimising data retrieval, reducing search times, and streamlining many computational processes. This article provides a comprehensive overview of common types of sorting algorithms, their runtime complexity, advantages, use cases, and applications.

Fundamental Concepts

Sorting refers to algorithms that rearrange elements of a dataset into a specified order, such as ascending or descending. Sorting enables efficient searching, ordering, and selection operations to be performed on data.

The importance of efficient sorting cannot be understated. It enables databases to quickly order and retrieve records, search engines to return relevant results faster, and analytics applications to process data effectively.

Types of sorting
Types of sorting

Comparison Vs Non Comparison Based Types Of Sorting Algorithms

Types of Sorting algorithms are generally classified into comparison and non-comparison based algorithms. Comparison sorts evaluate the relative order of elements by directly comparing them. Non-comparison sorts use techniques like bucketing, counting Occurrences, or extracting digits to indirectly determine sort order.

ParameterComparison Based SortingNon-Comparison Based Sorting
Basis of SortingCompares elements directly to determine orderUses keys like digits, frequency etc. to determine order
Time ComplexityO(n2) for basic sorts, O(nlogn) for efficient sortsO(n+k) for linear sorts, O(nk) for radix sort
Space ComplexityIn-place possible e.g. quicksortUse additional memory e.g. counting sort
StabilityCan be stable or unstableOften stable
Data TypesGeneral data types like integers, floats, strings etc.Integers and distinct data types for counting, radix sorts
ExamplesInsertion sort, merge sort, heapsortCounting sort, radix sort, bucket sort
ComparisonsDirect comparison of elementsSort based on keys like digit frequency
ImplementationCompare elements using comparisons operatorsCount occurrences, extract digits, use buckets
EfficiencyQuadratic basic sorts, nlogn efficient sortsLinear time possible for counting, bucket sorts
Extra SpaceIn-place sorting possibleUse additional arrays, buckets
StabilityUnstable possible e.g. quicksortOften stable e.g. counting sort
AdaptabilityAdaptive sorting possible e.g. timsortNot adaptive, fixed algorithms
ParallelizationChallenging to parallelizeBetter opportunities for parallelism
Comparison Vs Non Comparison Based Types Of Sorting Algorithms

Types of Sorting Algorithms

Elementary Sorting Algorithms

Elementary sorting algorithms conceptually demonstrate sorting, but have quadratic time complexity which limits efficiency.

Here are detailed explanations of bubble sort, selection sort, and insertion sort algorithms along with example working code implementations in Java, C, C++, and Python:

Bubble Sort

Bubble sort works by comparing adjacent elements in a list and swapping them if they are not in the intended order. This process is repeated until no more swaps are required, indicating the list is sorted.

Algorithm

Start with first element

Compare with next element, swap if not in order

Advance to next pair, repeat comparisons and swaps

Repeat process until no more swaps needed

Pseudocode
// PseudoCode For Bubble Sort

bubbleSort(arr[]):

  n = length(arr)

  for i = 0 to n-1 do:

    for j = 0 to n-i-1 do:

      if arr[j] > arr[j+1] 
        swap(arr[j], arr[j+1])
Walkthrough

Consider the array [5, 1, 4, 2, 8]

  • First pass:
    • (5, 1) → swap since 5 > 1 → [1, 5, 4, 2, 8]
    • (5, 4) → swap since 5 > 4 → [1, 4, 5, 2, 8]
    • (5, 2) → swap since 5 > 2 → [1, 4, 2, 5, 8]
    • (5, 8) → No swap
  • Second pass:
    • (4, 2) → swap since 4 > 2 → [1, 2, 4, 5, 8]
    • (4, 5) → No swap
    • (4, 8) → No swap
  • Third pass:
    • (2, 4) → swap since 2 < 4 → [1, 2, 4, 5, 8]
    • No more swaps required, sorted.

After n-1 passes, array is sorted.

Properties
  • Time Complexity: O(n2) worst and average case.
  • Space Complexity: O(1), in-place sorting.
  • Stable sorting algorithm.
  • Simple implementation but highly inefficient for large data sets.
Code Examples
Java
// Types of Sorting algorithms : Bubble Sort  Code in Java

void bubbleSort(int arr[]) {
  int n = arr.length;
  for(int i=0; i<n-1; i++) {
    for(int j=0; j<n-i-1; j++) {
      if(arr[j] > arr[j+1]) {
        // swap elements
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}
C
// Types of Sorting algorithms : Bubble Sort  Code in C

void bubbleSort(int arr[], int n){

  for(int i=0; i<n-1; i++){
    for(int j=0; j<n-i-1; j++){
      if(arr[j] > arr[j+1]){
        // swap elements
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}
C++
// Types of Sorting algorithms :  Bubble Sort  Code in C++

void bubbleSort(int arr[], int n){

  for(int i=0; i<n-1; i++){
    for(int j=0; j<n-i-1; j++){
      if(arr[j] > arr[j+1]){
        // swap elements 
        int temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
}
Python
# Types of Sorting algorithms :  Bubble Sort  Code in Python

def bubbleSort(arr):
  n = len(arr)

  for i in range(n-1):
    for j in range(n-i-1):
      if arr[j] > arr[j+1]:
        # swap elements
        arr[j], arr[j+1] = arr[j+1], arr[j]

Selection Sort

Selection sort selects the minimum element from the unsorted portion in each pass and places it at the end of the sorted portion.

Algorithm

Set first element as minimum

Compare minimum to next element, change if smaller

After traversing array, swap minimum with first element

Repeat process reducing unsorted portion

Pseudocode
//PseudoCode for Selection Sort

selectionSort(arr[]):

  n = length(arr)

  for i = 0 to n-1 do:

    minIndex = i

    for j = i+1 to n do:

      if arr[j] < arr[minIndex]
        minIndex = j

    swap(arr[i], arr[minIndex]) 
Walkthrough

Consider the array [5, 3, 1, 2, 4]

  • First pass:
  • Current min is index 0 (value 5)
  • Iterate rest of array, update min to index 2 (value 1)
  • After pass, swap 5 and 1 → [1, 3, 5, 2, 4]
  • Second pass:
  • Current min is index 1 (value 3)
  • Iterate rest of array, no change in min
  • After pass, no swap required → [1, 3, 5, 2, 4]
  • Third pass:
  • Current min is index 2 (value 5)
  • Iterate rest of array, update min to index 3 (value 2)
  • After pass, swap 5 and 2 → [1, 2, 5, 3, 4]

Repeat process, incrementing starting point each pass.

After n-1 passes, array is sorted.

Properties

  • Time Complexity: O(n2) worst and average case.
  • Space Complexity: O(1), in-place sorting.
  • Unstable sorting algorithm.
  • Simple implementation but inefficient for large data sets.
Code Examples
Java
// Types of Sorting algorithms: Selection Sort Code In Java

void selectionSort(int arr[]) {
   int n = arr.length;
   for(int i=0; i<n-1; i++) {
     int min = i;
     for(int j=i+1; j<n; j++){
       if(arr[j] < arr[min]) {
         min = j;
       }
     }
     // Swap min element with first element
     int temp = arr[min];
     arr[min] = arr[i];
     arr[i] = temp;
   }
}
C
// Types of Sorting algorithms: Selection Sort Code In C

void selectionSort(int arr[], int n) {
  int i, j, min;

  for(i=0; i<n-1; i++) {
    min = i;
    for(j=i+1; j<n; j++){
      if(arr[j] < arr[min]) {
        min = j;
      }
    }  
    // Swap min element with first element
    int temp = arr[min];
    arr[min] = arr[i];
    arr[i] = temp;
  }
}
C++
// Types of Sorting algorithms: Selection Sort Code In C++
void selectionSort(int arr[], int n){

  for(int i=0; i<n-1; i++){
    int min = i;
    for(int j=i+1; j<n; j++){
      if(arr[j] < arr[min]){
        min = j;  
      }
    }
    // Swap min element with first element
    int temp = arr[min];
    arr[min] = arr[i];
    arr[i] = temp;
  }
}
Python
# Types of Sorting algorithms: Selection Sort Code In Python

def selectionSort(arr):

  for i in range(len(arr)-1):
    min = i
    for j in range(i+1, len(arr)):
      if arr[j] < arr[min]:
        min = j
    # Swap minimum with first element        
    arr[i], arr[min] = arr[min], arr[i]

Insertion Sort

Insertion sort is a simple sorting algorithm that works by inserting each element into its correct position in the sorted portion of an array.

Algorithm

The array is virtually split into a sorted and unsorted portion. Initially, the sorted portion contains just the first element.

A current element is selected from the unsorted portion. This is compared to the elements in the sorted portion from right to left.

If the current element is greater than the element in the sorted portion, it is moved to the right. This process is repeated until an element smaller than the current is found.

Once the correct position for the current is found, it is inserted into the sorted portion.

Steps 2-4 are repeated for the remaining elements until the whole array is sorted.

Pseudocode
// Types of Sorting techniques: Psuedocode for Insertion Sort

For i = 1 to n-1
  key = arr[i]
  j = i-1

  While j >= 0 and arr[j] > key
    arr[j+1] = arr[j] 
    j = j-1

  arr[j+1] = key
Walkthrough

Consider the array [5, 2, 4, 6, 1, 3]

  • Start by assuming first element 5 is sorted. Unsorted portion is [2, 4, 6, 1, 3]
  • Take 2 as current element. Compare with 5. 2 < 5, so move 5 to right. Insert 2 before 5. Sorted portion is [2, 5].
  • Take 4 as current element. Compare with 5 and 2. Stop at 2 which is smaller. Insert 4 after 2. Sorted portion is [2, 4, 5].
  • Take 6 as current element. Compare with 5. 6 > 5, so insert after 5. Sorted portion is [2, 4, 5, 6].
  • Take 1 as current element. Compare with 6, 5, 4, 2. Insert before 2. Sorted portion is [1, 2, 4, 5, 6].
  • Take 3 as current element. Insert after 2. Sorted portion is [1, 2, 3, 4, 5, 6].
Properties
  • Space complexity: O(1), in-place sorting
  • Stable sorting algorithm
  • Adaptive algorithm – efficient for partially sorted data
  • Best Case: O(n) – Array is already sorted
  • Average Case: O(n^2)
  • Worst Case: O(n^2)

Insertion sort is simple to implement but inefficient for large data sets. It is more efficient than bubble sort and selection sort. The algorithm is stable and adaptive, making it useful in practice, especially when data is mostly sorted.

Code Example
Java
// Types of Sorting techniques: Insertion Sort Code in Java

void insertionSort(int arr[]) {
  for(int i=1;i<arr.length;i++){
    int temp = arr[i];
    int j = i-1;
    while(j>=0 && arr[j]>temp){
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = temp;
  }
}
C
//  Types of Sorting techniques: Insertion Sort Code in C

void insertionSort(int arr[], int n){

  for(int i=1; i<n; i++){
    int temp = arr[i];
    int j = i-1;
    while(j>=0 && arr[j]>temp){
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = temp;
  }
}
C++
// Types of Sorting techniques: Insertion Sort Code in C++ 
void insertionSort(int arr[], int n){

  for(int i=1; i<n; i++){
    int temp = arr[i];
    int j = i-1;
    while(j>=0 && arr[j]>temp){
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = temp;
  }
}
Python
#  Types of Sorting techniques: Insertion Sort Code in Python

def insertionSort(arr):

  for i in range(1, len(arr)):
    temp = arr[i]
    j = i-1
    while j>=0 and arr[j]>temp:
      arr[j+1] = arr[j]
      j -= 1
    arr[j+1] = temp

Efficient Sorting Algorithms

Efficient algorithms use techniques like divide-and-conquer to achieve improved time complexities compared to elementary algorithms.

Merge Sort

Merge sort works by recursively splitting the array into halves, sorting each half, and merging them back together in sorted order.

Algorithm

If the array has 0 or 1 element, it is already sorted. Otherwise, split the array in half.

Recursively sort each half by repeating the splitting process until arrays of 0 or 1 element are reached.

Merge the sorted subarrays together to produce the final sorted array.

Merge Process:

  1. Create pointers for first elements of each array. Compare elements, add smaller one to output.
  2. Advance pointer of array whose element was added. When a pointer reaches end of an array, add remaining elements of other array.
PseudoCode
//  Types of Sorting techniques: PseudoCode for Merge Sort

mergeSort(arr[], left, right):

  if right > left:

    mid = (left + right)/2

    mergeSort(arr, left, mid)

    mergeSort(arr, mid+1, right)

    merge(arr, left, mid, right)


merge(arr[], left, mid, right):

  create temp arrays L[] and R[] 

  copy arr elements to L[] and R[]

  i = j = k = 0

  while i < n1 and j < n2:

    if L[i] <= R[j]:

      arr[k] = L[i]
      i++

    else:

      arr[k] = R[j]
      j++

    k++

  copy remaining elements of L[] and R[] to arr[] 
Walkthrough

Consider the array [38, 27, 43, 3, 9, 82, 10]

  • Divide array into [38, 27, 43, 3] and [9, 82, 10]
  • Divide first subarray into [38, 27] and [43, 3] and second subarray into [9] and [82, 10]
  • Merge [38, 27] and [43, 3] into [3, 27, 38, 43]
  • Merge [9] and [82, 10] into [9, 10, 82]
  • Merge previous sorted arrays into [3, 9, 10, 27, 38, 43, 82]
Properties
  • Space complexity: O(n) auxiliary
  • Stable sorting algorithm
  • In-place merging is complex
  • Worst case performance: O(nlogn)

Overall, merge sort is an efficient, stable sorting algorithm optimal for larger datasets. Its divide and conquer strategy reduces time complexity.

Code Examples
Java
//  Types of Sorting techniques: Merge Sort Code in Java

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

void merge(int arr[], int l, int m, int r) {
  // Merge code
}
C
//  Types of Sorting techniques: Merge Sort Code in C 
void mergeSort(int arr[], int l, int r){
  if(l < r){
    int m = l+(r-l)/2;
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);
    merge(arr, l, m, r); 
  }
}

void merge(int arr[], int l, int m, int r){
  // Merge code
}
C++
//  Types of Sorting techniques: Merge Sort Code in C++
void mergeSort(int arr[], int l, int r){
  if(l < r){
    int m = l+(r-l)/2;
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);
    merge(arr, l, m, r);
  }  
}

void merge(int arr[], int l, int m, int r){
   // Merge code 
}
Python
#  Types of Sorting techniques: Merge Sort Code in Python

def mergeSort(arr,l,r):
  if l < r:
    m = (l+(r-1))//2
    mergeSort(arr, l, m)
    mergeSort(arr, m+1, r)
    merge(arr, l, m, r)

def merge(arr, l, m, r):
  # Merge code  

Quicksort

Quicksort is an efficient divide and conquer sorting algorithm. It works by selecting a ‘pivot’ element and partitioning the array around it such that elements less than the pivot are to the left and greater elements are to the right.

Algorithm

Select the last element as pivot

Partition the array by placing elements less than pivot to the left and greater than pivot to the right of pivot.

Recursively apply the same process to left and right subarrays.

Partitioning:

  1. Initialize left pointer at first element and right pointer at last element.
  2. Increment left pointer until an element greater than pivot is found. Increment right pointer until an element less than pivot is found.
  3. Swap the elements and repeat process until pointers cross.
  4. Place pivot between the pointers.

Pivot Selection:

  • First, middle or random element can be picked as pivot. Last element is commonly used.
  • Median of medians method provides optimal pivot selection.
Pseudocode
//  Types of Sorting techniques: Pseudocode for QuickSort

quickSort(arr[], low, high) {

  if (low < high) {

    pivotIndex = partition(arr, low, high) 

    quickSort(arr, low, pivotIndex)

    quickSort(arr, pivotIndex + 1, high)
  }
}

partition(arr[], low, high) {

  // Partitioning logic

  return pivotIndex; 
}
Walkthrough

Consider the array [9, 6, 5, 3, 1, 8, 7, 2, 4]

  • Select last element 4 as pivot
  • Initialization: Left pointer = 0, right pointer = 8
  • Increment left pointer to 1, swap 9 and 6
  • Array: [6, 9, 5, 3, 1, 8, 7, 2, 4]
  • Increment right pointer to 7, swap 4 and 2
  • Array: [6, 9, 5, 3, 1, 8, 2, 7, 4]
  • Increment left pointer to 3, swap 5 and 3
  • Array: [6, 9, 3, 5, 1, 8, 2, 7, 4]
  • Pointers crossed. Pivot placed between them.
  • Array: [3, 2, 1, 5, 6, 8, 9, 7, 4]
  • Quicksort applied recursively on subarrays [3, 2, 1] and [5, 6, 8, 9, 7]
Properties
  • Time Complexity:
  • Best case: O(nlogn)
  • Average case: O(nlogn)
  • Worst case: O(n^2)
  • Space Complexity: O(logn)
  • In place sorting algorithm
  • Unstable sorting algorithm

Quicksort is efficient in practice, provides good average case performance and extra space usage is only for recursive calls. However, worst case is quadratic making it unsuitable for certain scenarios.

Code Examples
Java
//  Types of Sorting techniques: Quick Sort Java Program

void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pivot = partition(arr, low, high);

    quickSort(arr, low, pivot-1);
    quickSort(arr, pivot+1, high);
  }
}

int partition(int arr[], int low, int high) {
  int pivot = arr[high]; 
  int i = (low-1);

  for (int j=low; j<high; j++) {
    if (arr[j] <= pivot) {
      i++;
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }

  int temp = arr[i+1];
  arr[i+1] = arr[high];
  arr[high] = temp;

  return i+1;
}
C++
//  Types of Sorting techniques: Quick Sort Java Program C++

void quickSort(int arr[], int low, int high) {
  if (low < high) {
    int pivot = partition(arr, low, high);

    quickSort(arr, low, pivot-1); 
    quickSort(arr, pivot+1, high);
  }
}

int partition (int arr[], int low, int high) {
  int pivot = arr[high];
  int i = (low - 1);

  for (int j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }

  swap(arr[i+1], arr[high]);
  return (i+1);
}
C
//  Types of Sorting techniques: Quick Sort Java Program C

void quickSort(int arr[], int low, int high){
  if (low < high) {
    int pivot = partition(arr, low, high);

    quickSort(arr, low, pivot-1);  
    quickSort(arr, pivot+1, high);
  }
}

int partition (int arr[], int low, int high) {
  int pivot = arr[high];
  int i = (low - 1);

  for (int j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(&arr[i], &arr[j]);
    }
  }

  swap(&arr[i+1], &arr[high]);
  return (i+1);
}
Python
//  Types of Sorting techniques: Quick Sort Java Program Python 

def quickSort(arr, low, high):
  if low < high:
    pivot = partition(arr, low, high)

    quickSort(arr, low, pivot-1)
    quickSort(arr, pivot+1, high)

def partition(arr, low, high):
  pivot = arr[high]
  i = low-1

  for j in range(low, high):
    if arr[j] <= pivot:
      i += 1
      arr[i], arr[j] = arr[j], arr[i]

  arr[i+1], arr[high] = arr[high], arr[i+1]
  return i+1

Heapsort

Heapsort uses a binary heap data structure to efficiently sort an array. It converts the array into a max heap, repeatedly extracts the maximum element, and places it at the end of the array.

Algorithm Of Heap Sort

Convert the array into a max heap by heapifying it from the midpoint down to the first element.

Swap the root (maximum value) with the last element of the heap.

Discard the last element from the heap and readjust to maintain max heap property.

Repeat steps 2 and 3 reducing the heap size by 1 each time until only one element remains.

Heapify

The heapify procedure converts a subtree into a max heap by comparing nodes with children and swapping if necessary to maintain the heap order property.

Build Max Heap

Heapify is called on each subtree from midpoint to first element to convert the full array into a max heap.

Pseudocode
 // Types of Sorting techniques : PseudoCode and algorithm of heap sort

heapSort(arr):

  buildMaxHeap(arr)

  for i = n to 1:

    swap arr[1] and arr[i] 

    heapify(arr, 1, i-1)

buildMaxHeap(arr):

  for i = n/2 to 1:

    heapify(arr, i, n) 

heapify(arr, i, n):

  largest = i 

  l = 2*i, r = 2*i + 1

  if l <= n and arr[l] > arr[largest]:

    largest = l

  if r <= n and arr[r] > arr[largest]: 

    largest = r

  if largest != i:

    swap arr[i] and arr[largest]

    heapify(arr, largest, n)
Walkthrough

Consider the array [6, 5, 3, 7, 2, 8, 4]

  1. Heapify subtree [5, 3]: Swap 5 and 3 since 3 is larger. Heap is [6, 3, 5, 7, 2, 8, 4]
  2. Heapify subtree [6, 3, 5]: No change needed.
  3. Heapify full array from midpoint: [8, 6, 7, 4, 2, 5, 3]
  4. Swap root 8 with last element 3: [3, 6, 7, 4, 2, 5, 8]
  5. Discard 8, heapify reduced heap: [5, 6, 7, 4, 2, 3]
  6. Swap root 5 with last element 2: [2, 6, 7, 4, 3, 5]
  7. Discard 5, heapify: [4, 6, 7, 2, 3]
  8. Continue process until 1 element left: [2, 3, 4, 5, 6, 7, 8]

The heapsort algorithm efficiently sorts the array in O(nlogn) time by exploiting the heap data structure.

Code Examples
Java
//  Types of Sorting algorithms : Heap Sort 

void heapSort(int[] arr, int n) {
  // heapify 
  for (int i = n/2 - 1; i >= 0; i--) 
    heapify(arr, n, i);

  // extract elements
  for (int i=n-1; i>=0; i--) { 
    int temp = arr[0];
    arr[0] = arr[i]; 
    arr[i] = temp;
    heapify(arr, i, 0);
  }
}

C++

// Heap Sort C++
void heapSort(int arr[], int n) {
  // heapify
  for (int i = n/2 - 1; i >= 0; i--)
    heapify(arr, n, i);

  // extract elements
  for (int i=n-1; i>=0; i--) {
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
  } 
}

C

// Heap Sort in C

void heapSort(int arr[], int n) {
  
  // heapify
  for (int i = n/2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // extract elements
  for (int i=n-1; i>=0; i--) {
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
  }
}

Python

# Heap Sort
def heapify(arr, n, i):
  # heapify logic

def heapSort(arr):
  n = len(arr)

  # heapify
  for i in range(n//2 - 1, -1, -1):
    heapify(arr, n, i)

  # extract elements
  for i in range(n-1, 0, -1):
    arr[i], arr[0] = arr[0], arr[i] 
    heapify(arr, i, 0)

Non-Comparison Based Sorting

Non-comparison sorts use alternative techniques like counting, radixes, or bucketing. These allow improved efficiency for certain data types.

Here are detailed explanations of counting sort, bucket sort, radix sort, timsort and shellsort algorithms including the algorithm, walkthrough and properties:

Counting Sort

Counting sort is an efficient non-comparison sorting algorithm that sorts elements in linear time by determining the count of each unique element in the array.

Algorithm

Find the maximum and minimum values in the array to determine the range of elements.

Create a count array/list of size equal to the range, with all values initialized to 0.

Iterate through the input array and increment count[i] for each element with value i.

Modify count such that each index stores the cumulative sum of previous counts.

Output each element from input array by looking up its index/count in count array.

Pseudocode
//  Types of Sorting algorithms: Pseudocode for counting sort

countSort(array):

  max = find largest element in array
  min = find smallest element in array

  count = create array of size (max-min+1) with all 0s

  for each element in array:
    count[element]++

  for i = 1 to max-min: 
    count[i] += count[i-1]

  for i = n-1 to 0:
    output[count[array[i]]-1] = array[i]
    count[array[i]]--

  return output
Walkthrough

Input array: [1, 4, 7, 3, 4, 6, 4]

  1. Find min and max values as 1 and 7
  2. Create count array of size 7: [0, 0, 0, 0, 0, 0, 0]
  3. Update count array based on input: [0, 2, 1, 1, 0, 1, 2]
  4. Cumulative counts: [0, 2, 3, 4, 4, 5, 7]
  5. Output array using count: [1, 3, 6, 4, 4, 4, 7]
Code Examples
Java
//  Types of Sorting algorithms: Counting Sort In Java

void countingSort(int[] arr) {
  int max = Arrays.stream(arr).max().getAsInt();
  int min = Arrays.stream(arr).min().getAsInt();
  int range = max - min + 1;
  int count[] = new int[range];
  int output[] = new int[arr.length];
  // count occurrences
  for (int i = 0; i < arr.length; i++) {
    count[arr[i] - min]++;
  }
  // cumulative count 
  for (int i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }
  // fill output array
  for (int i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--;
  } 
}

C++

//  Types of Sorting algorithms: Counting Sort In C++

void countingSort(int arr[], int n) {
  int max = *max_element(arr, arr+n);
  int min = *min_element(arr, arr+n);
  int range = max - min + 1;
  int count[range], output[n];
  fill(count, count + range, 0);

  // store counts
  for (int i = 0; i < n; i++)
    count[arr[i]-min]++;
  
  // cumulative counts
  for (int i = 1; i < range; i++) 
    count[i] += count[i-1];

  // fill output array
  for (int i = n-1; i >= 0; i--) {
    output[count[arr[i]-min]-1] = arr[i];
    count[arr[i]-min]--;
  }
}

C

//  Types of Sorting algorithms: Counting Sort In C

void countingSort(int arr[], int n) {
  
  int max = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > max) 
      max = arr[i];
  }

  int min = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] < min)
      min = arr[i]; 
  }

  int range = max - min + 1;
  int count[range];
  int output[n];

  for (int i = 0; i < range; i++) {
    count[i] = 0;
  }

  // store counts of each element
  for (int i = 0; i < n; i++) {
    count[arr[i] - min]++; 
  }

  // cumulative counts
  for (int i = 1; i < range; i++) {
    count[i] += count[i - 1];
  }

  // fill output array
  for (int i = 0; i < n; i++) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--; 
  }
}

Python

#  Types of Sorting algorithms: Counting Sort  In Python

def countingSort(arr):
  max_val = max(arr)
  min_val = min(arr)
  range_val = max_val - min_val + 1

  count = [0 for _ in range(range_val)]
  output = [0 for _ in range(len(arr))]

  # store count of each element
  for i in arr:
    count[i-min_val] += 1
  
  # cumulative counts
  for i in range(1, len(count)):
    count[i] += count[i-1]

  # fill output array
  for i in range(len(arr)-1, -1, -1):
    output[count[arr[i] - min_val] - 1] = arr[i]
    count[arr[i] - min_val] -= 1

  for i in range(len(arr)):
    arr[i] = output[i]

Properties:

  • Time Complexity: O(n+k) where n is number of elements, k is range of input
  • Space Complexity: O(n+k) for count array
  • Stable sorting algorithm
  • Efficient for small integer keys within a specific range
  • Not in-place, requires extra memory

Counting sort works well for sorting small positive integers with a tight range by exploiting the frequency data of input elements.

Bucket Sort

Bucket sort partitions elements into buckets representing ranges, then sorts each bucket individually.

Algorithm

Initialize buckets covering value range

Distribute elements into buckets

Sort individual buckets using any sorting algorithm

Concatenate buckets in order

Pseudocode
//  Types of Sorting algorithms: Pseudocode for bucketsort

bucketSort(array, k):

// k is the number of buckets 

initialize k empty buckets  

for each element in array:

  insert element into appropriate bucket

for i = 1 to k:

  sort elements in bucket i using insertion sort

concatenate sorted buckets 

return concatenated array
Walkthrough

Original array: [0.25, 0.5, 0.75, 0.1]

Bucket ranges: [0-0.25), [0.25-0.5), [0.5-0.75), [0.75-1]

Distribute into buckets:

B1: [0.1]

B2: [0.25]

B3: [0.5, 0.75]

Sort buckets:

B1: [0.1]

B2: [0.25]

B3: [0.5, 0.75]

Concatenate: [0.1, 0.25, 0.5, 0.75]

Properties
  • Time Complexity: O(n+k)
  • Space Complexity: O(n+k)
  • Stable sort based on sub-sort

Bucket allows sorting of floats and non-uniform distributions efficiently.

Code Examples
Java
//  Types of Sorting algorithms: Bucket Sort In Java

void bucketSort(float[] arr) {
  int n = arr.length;
  @SuppressWarnings("unchecked")
  List<Float>[] buckets = new List[n];

  // initialize buckets  
  for (int i = 0; i < n; i++) {
    buckets[i] = new ArrayList<>(); 
  }

  // distribute elements into buckets
  for (int i = 0; i < n; i++) {
    int bucketIdx = (int)arr[i] * n;
    buckets[bucketIdx].add(arr[i]);
  }

  // sort individual buckets
  for (int i = 0; i < n; i++) {
    Collections.sort(buckets[i]);
  }

  // concatenate buckets
  int index = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0, size = buckets[i].size(); j < size; j++) {
      arr[index++] = buckets[i].get(j);
    }
  }
}
C
//  Types of Sorting algorithms: Bucket Sort In C

void bucketSort(float arr[], int n) {

  int i, j;
  float buckets[n][n];

  // put elements into buckets
  for (i = 0; i < n; i++) {
    int bucketIdx = n * arr[i];
    buckets[bucketIdx][j++] = arr[i]; 
  }

  // sort individual buckets
  for (i = 0; i < n; i++) {
    qsort(buckets[i], j, sizeof(float), compare); 
  }

  // concatenate buckets
  j = 0; 
  for (i = 0; i < n; i++) {
    int k;
    for (k = 0; k < n; k++) {
      arr[j++] = buckets[i][k];
    }
  }
}
C++
//  Types of Sorting algorithms: Bucket Sort In C++ 

void bucketSort(float arr[], int n) {
  vector<float> buckets[n];

  // put elements in buckets
  for (int i=0; i<n; i++) {
    int bucketIdx = arr[i] * n;
    buckets[bucketIdx].push_back(arr[i]);
  }

  // sort individual buckets
  for (int i = 0; i < n; i++) 
    sort(buckets[i].begin(), buckets[i].end());

  // concatenate buckets
  int index = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < buckets[i].size(); j++) {
      arr[index++] = buckets[i][j];
    }
  }
}
Python
# Types of Sorting algorithms: Bucket Sort In Python

def bucketSort(arr):
  max_val = max(arr)
  size = len(arr)
  buckets_list = [[] for _ in range(size)]

  # put elements in different buckets
  for i in range(size):
    j = int(size * arr[i])
    if j != size:
      buckets_list[j].append(arr[i])
    else:
      buckets_list[size - 1].append(arr[i])

  # sort individual buckets
  for i in range(size):
    buckets_list[i] = sorted(buckets_list[i]) 

  # concatenate buckets
  k = 0
  for i in range(size):
    for j in range(len(buckets_list[i])):
      arr[k] = buckets_list[i][j]
      k += 1

  return arr

Radix Sort

Radix sort stably sorts array by digits at each position iteratively from least to most significant.

Algorithm
  1. Extract digits from same position using digit as key
  2. Sort array using digit key
  3. Repeat for next digit positions
Pseudocode
 // Types of Sorting algorithms: Pseudocode For Radixsort

radixSort(array, d):
 // d is number of digits in largest number
 for i = 1 to d:
   use counting sort on array by ith digit
   return array
Walkthrough

Array: 329, 457, 657, 839, 436, 720

Ones place: [9, 7, 7, 9, 6, 0] -> [720, 329, 436, 839, 457, 657]

Tens place: [329, 436, 457, 657, 720, 839]

Hundreds place: [329, 436, 457, 657, 720, 839]

Properties
  • Time Complexity: O(nk)
  • Space Complexity: O(n+k)
  • Stable sort

Radix efficiently sorts integers stably in linear time.

Code Example
Java
//  Types of Sorting algorithms: Radix Sort 

void radixSort(int[] arr) {
  int max = Arrays.stream(arr).max().getAsInt();
  // sort by each digit
  for (int exp = 1; max/exp > 0; exp *= 10) {
    countSort(arr, exp);
  }
}

void countSortForRadix(int[] arr, int exp) {
  // count sort logic using digit at exp
}
C
//  Types of Sorting algorithms: Radix Sort
void radixSort(int arr[], int n) {

  int m = getMax(arr, n);

  // sort by each digit
  for (int exp = 1; m/exp > 0; exp *= 10) {
    countSort(arr, n, exp);
  }
}

// count sort logic for radix
C++
//  Types of Sorting algorithms: Radix Sort
void radixSort(int arr[], int n) {
  int max = *max_element(arr, arr+n);

  // sort by each digit
  for (int exp = 1; max/exp > 0; exp *= 10)
    countSort(arr, n, exp); 
}

void countSort(int arr[], int n, int exp) {
  // count sort logic on digit at exp
}
Python
#  Types of Sorting algorithms: Radix Sort
def countingSortForRadix(exp, arr):
  # count sort logic for radix

def radixSort(arr):
  max_element = max(arr)
  place = 1
  while max_element // place > 0:
    countingSortForRadix(place, arr)
    place *= 10

Shellsort

Shellsort sorts array by comparing elements separated by gaps that are reduced each iteration.

Algorithm

Initialize gap value

Sort array using insertion sort and gap

Reduce gap and repeat sorting

Pseudocode
// PseudoCode For Shell Sort

shellSort(array, n):
 initialize gap = n/2
 while gap > 0:

   for i = gap to n:

   insert array[i] among previous using insertion sort and gap
   reduce gap to gap/2

   return array

Shell sort improves on insertion sort by comparing across gaps.

Properties
  • Time Complexity: O(nlogn) down to O(n^1.25)
  • Space Complexity: O(1)
  • Unstable sort

Shell sort code

Timsort

Timsort combines insertion sort and mergesort. It sorts small chunks with insertion sort, then merges the chunks.

Algorithm

Divide array into sorted chunks with insertion sort

Merge chunks using mergesort when they reach threshold size

Properties
  • Time Complexity: O(n log n)
  • Space Complexity: O(n)
  • Stable sort
  • Adaptive optimization for real-world data

Timsort is optimized for performance on many real-world datasets.

Sorting in Programming Languages

Built-in sorting functions and libraries are optimized for convenience and efficiency.

Here are different ways of using different types of sorting in different programming languages:

Python

  • sorted() – Returns a sorted list from an iterable
  • list.sort() – Sorts a list in-place
  • Uses Timsort (hybrid of mergesort and insertion sort)
  • key and reverse params for custom sorting logic

Java

  • Arrays.sort() – Sorts primitive arrays
  • Collections.sort() – Sorts object collections
  • Uses optimized quicksort and merge sort implementations
  • Comparator interfaces for custom sorting

C++

  • std::sort() – General purpose sort function
  • std::stable_sort() – Stable sort function
  • Internally uses introsort – introspective sort
  • Overload comparison operators or provide comparator function for custom sorts

Types of Sorting In C

  • qsort() – Implements quicksort algorithm
  • comparator function required for custom sorting logic
  • Not a stable sort
  • Pointer friendly for arrays

JavaScript

  • array.sort() – Sorts array in-place
  • compareFunction optional for custom sort order
  • Uses quicksort V8 engine optimization
  • Works on any iterable objects

Go

  • sort package – Sort() and Stable() functions
  • sort.Interface interface for custom sorts
  • Hybrid merge+insertion sort for efficiency
  • Concurrency-safe versions available

Most languages provide built-in highly optimised sorting functions while allowing customisation like comparator functions.

Comparison of Different Types Of Sorting Techniques

Here is a comparison of different types of sorting techniques :

Comparison of different types of sorting
Comparison of different types of sorting
  • Bubble, insertion and selection sorts are elementary sorts with quadratic time complexity.
  • Merge, quick, heap are efficient general purpose sorts with O(nlogn) complexity.
  • Counting, bucket and radix exploit properties of input for improved efficiency.
  • Shell and timsort use hybrid approaches for real-world optimization.
  • Stability, in-place requirements, input size etc. factor into choosing the best sort.

Applications of Sorting

  • Databases rely on efficient sorting for quickly ordering and indexing records.
  • Web search engines use sorting to return most relevant results first.
  • Analytics tasks require sorting for summarization, pattern analysis, and data processing.

Conclusion

Sorting is an essential concept in computer science with widespread applications. Efficient sorting enables processing and retrieval of data in diverse computing areas. Further exploration of advanced sorting, implementations, and real-world use cases is encouraged.In this articile we covered types of sorting algorithms along with algorithms and code in various programming language.

Try out our free resume checker service where our Industry Experts will help you by providing resume score based on the key criteria that recruiters and hiring managers are looking for.

References

  • Introduction to Algorithms by Thomas H. Cormen et al.
  • Algorithms by Robert Sedgewick and Kevin Wayne
  • The Art of Computer Programming by Donald Knuth

FAQ Regarding Types Of Sorting Techniques

When should I use a stable vs unstable sorting algorithm?

Stable algorithms maintain order of elements with equal keys. Use stable sort when relative order needs to be maintained, like sorting names by surname.

When would bucket sort be more efficient than quicksort?

Bucket sort works well when input is uniformly distributed. It can achieve linear time complexity compared to quicksort’s nlogn.

What are some examples of adaptive sorting algorithms?

Timsort and introsort are examples of adaptive sorts that can optimize based on partially sorted data.

How does radix sort achieve linear time complexity?

Radix sort exploits the integer digit structure by sorting on each position iteratively. This avoids comparisons between elements.

What is a hybrid sorting algorithm?

Hybrid algorithms combine approaches from multiple sorting techniques like timsort using insertion sort and merge sort.

90% of Tech Recruiters Judge This In Seconds! 👩‍💻🔍

Don’t let your resume be the weak link. Discover how to make a strong first impression with our free technical resume review!

Related Articles

Combination Sum leetcode

Combination Sum LeetCode 39 Solution

In this article we will solve Combination Sum LeetCode Problem which is a very good backtracking question. Difficulty: Medium, Asked-in: Amazon, Adobe. Problem Statement Given an array of distinct integers and a target, you

Why Aren’t You Getting Interview Calls? 📞❌

It might just be your resume. Let us pinpoint the problem for free and supercharge your job search. 

Newsletter

Don’t miss out! Subscribe now

Log In