Classification of Sorting Algorithms

July 9, 2025

Sorting Algorithms and its types

Sorting Algorithms and its types – Sorting is a basic concept in computer science and programming. Whether you are dealing with numbers, words, files, or database entries, sorting helps make data more organized and easier to manage. For example, think about searching for a contact in your phone or finding a book in a library. If the items are sorted, it becomes much faster and simpler.

Sorting algorithms are special techniques used to arrange data in a particular order, either ascending or descending. These algorithms are widely used in computer programming and data science to process, visualize, and store information efficiently.

Classification of sorting algorithms Based on Number of Comparisons
Based on Recursion
Based on Stability
Based on Method of Sorting

What are Sorting Algorithms?

Sorting algorithms are step-by-step methods used to rearrange elements in a list or array in a specific order. The most common orders are:

Ascending (e.g., 1, 2, 3, 4)
Descending (e.g., 9, 7, 5, 3)

Different sorting algorithms follow different techniques to achieve the final sorted list. Some are simple and easy to implement (like Bubble Sort), while others are faster and more efficient (like Merge Sort and Quick Sort).

Uses and Importance of Data Structure Sorting

Sorting is not just about arranging data. It plays a crucial role in many areas of computer science. Here’s why sorting is important:

Faster Searching Many searching algorithms like Binary Search work only on sorted data.

Data Organization Sorted data makes it easier to understand, analyze, and visualize.

Data Integrity Sorting helps in detecting duplicates or missing elements.

Efficient Algorithms Some advanced algorithms require pre-sorted input to work effectively.

Improved Performance Many real-world applications (e.g., databases, search engines, etc.) rely on sorting for better speed and performance.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Classification of Sort Algorithms

Sorting algorithms can be classified based on different factors:

1. Based on Number of Comparisons

Comparison-based (e.g., Quick Sort, Merge Sort)
Non-comparison-based (e.g., Counting Sort, Radix Sort)

2. Based on Recursion

Recursive (e.g., Merge Sort, Quick Sort)
Non-recursive (e.g., Bubble Sort, Insertion Sort)

3. Based on Stability

Stable (e.g., Bubble Sort, Merge Sort)
Unstable (e.g., Quick Sort, Heap Sort)

4. Based on Method of Sorting

Internal Sorting: Works on data in main memory.
External Sorting: Works on data in external memory (like files on disk).

Types of Sorting Algorithms in Data Structure

There are several sorting algorithms used in data structures. Some are basic and beginner-friendly, while others are advanced and more efficient. Here’s a list of popular sorting methods:

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
Heap Sort
Counting Sort
Radix Sort
Bucket Sort

Let’s understand each of them in detail.

Characteristics of Sorting Algorithms

When comparing sorting algorithms, we usually look at these characteristics:

Time Complexity: How fast the algorithm is.
Space Complexity: How much extra memory it uses.
Stability: Whether equal elements maintain their original order.
In-place Sorting: Whether sorting is done using only a small amount of extra space.
Comparison-based or Non-comparison-based: How the algorithm determines the order.

Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is sorted.

Algorithm:

Start from the first element.
Compare the current element with the next element.
If the current element is greater than the next, swap them.
Repeat steps 2-3 for each pair of adjacent elements in the list.
Repeat the entire process for all elements until no swaps are needed.

C++ Code – Bubble Sort:

Run

#include<iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for(int i = 0; i < n-1; i++) {
        bool swapped = false;
        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;
                swapped = true;
            }
        }
        // If no two elements were swapped in inner loop, array is sorted
        if(!swapped) break;
    }
}

void printArray(int arr[], int n) {
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    bubbleSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output:

Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90

Time Complexity:

Best Case O(n)
Average Case O(n²)
Worst Case O(n²)

Space Complexity:

O(1) – Bubble Sort is an in-place algorithm and does not require extra space.

Explanation:

The algorithm makes multiple passes through the array.
In each pass, adjacent elements are compared and swapped if required.
After each pass, the largest unsorted element bubbles up to its correct position at the end.
The inner loop reduces with each outer loop pass because the largest elements settle at the end.
The swapped flag optimizes the algorithm by stopping early if no swaps occurred in a pass.

Selection Sort

Selection Sort is a comparison-based sorting algorithm. It works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning of the sorted portion.

Algorithm:

Iterate from index 0 to n-1.
For each position i, find the minimum element in the remaining unsorted part (i to n-1).
Swap the found minimum element with the element at position i.
Repeat until the array is completely sorted.

C++ Code :

Run

#include<iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;

        // Find the index of the minimum element
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }

        // Swap the found minimum with the first element
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    selectionSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output:

Original array: 29 10 14 37 13 
Sorted array: 10 13 14 29 37

Explanation:

In the first iteration, the minimum element from the entire array is found and placed at the first position.
In the second iteration, the minimum of the remaining elements is placed at the second position, and so on.
Unlike Bubble Sort, Selection Sort makes fewer swaps.
However, it still performs O(n²) comparisons.

Time Complexity:

Best Case O(n²)
Average Case O(n²)
Worst Case O(n²)

Note: Number of comparisons remains the same in all cases.

Space Complexity:

O(1) – It’s an in-place algorithm and does not use any extra space.

Insertion Sort

Insertion Sort builds the sorted array one element at a time. It takes each element from the input and inserts it into its correct position in the sorted part of the array.

Algorithm:

Start from the second element (index 1) and compare it with the first.
Insert the second element into the correct position relative to the first.
Take the third element and insert it into the correct position among the first two.
Continue this process for all remaining elements.

C++ Code :

Run

#include<iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; // Move elements greater than key one position ahead while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // Insert the key at the correct position
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {9, 5, 1, 4, 3};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    insertionSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output:

Original array: 9 5 1 4 3 
Sorted array: 1 3 4 5 9

Explanation:

The algorithm divides the array into a sorted and an unsorted part.
At every step, the first element of the unsorted part is picked and inserted at the right position in the sorted part.
Works efficiently for small or nearly sorted arrays.

Time Complexity:

Best Case O(n)
Average Case O(n²)
Worst Case O(n²)

Space Complexity:

O(1) – It is an in-place algorithm.

Merge Sort

Merge Sort is a Divide and Conquer sorting algorithm. It divides the array into halves, recursively sorts them, and finally merges the sorted halves to produce the final sorted array.

Algorithm:

Divide the array into two halves.
Recursively sort each half using merge sort.
Merge the two sorted halves into one sorted array.

C++ Code :

Run

#include<iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary arrays
    int L[n1], R[n2];

    // Copy data to temp arrays L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Merge the temp arrays back into arr[left..right]
    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }

    // Copy the remaining elements
    while (i < n1)
        arr[k++] = L[i++];
    while (j < n2)
        arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);      // Sort first half
        mergeSort(arr, mid + 1, right); // Sort second half

        merge(arr, left, mid, right);   // Merge the sorted halves
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    cout << "Sorted array: ";
    printArray(arr, size);

    return 0;
}

Output:

Original array: 38 27 43 3 9 82 10 
Sorted array: 3 9 10 27 38 43 82

Time Complexity:

Best Case O(n logn)
Average Case O(n logn)
Worst Case O(n logn)

Space Complexity:

O(n) – Because it uses temporary arrays during merging.

Explanation:

Merge Sort recursively divides the array until each subarray contains one element.
Then it starts merging two sorted arrays at a time.
The merging is performed in such a way that the final array remains sorted.
It is stable, and works very well with large datasets.

Quick Sort

Quick Sort is a Divide and Conquer sorting algorithm. It picks a pivot element, partitions the array such that elements smaller than the pivot are on the left, and larger ones on the right, then recursively sorts the sub-arrays.

Algorithm:

Choose a pivot element from the array.
Partition the array into two subarrays:
- Elements less than or equal to pivot
- Elements greater than pivot
Recursively apply the same steps to each subarray.

C++ Code :

Run

#include<iostream>
using namespace std;

// Partition function
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Pivot element
    int i = low - 1;       // Index of smaller element

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]); // Swap if element is smaller than pivot
        }
    }
    swap(arr[i + 1], arr[high]); // Place pivot at the correct position
    return (i + 1);
}

// QuickSort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // pi = partition index

        quickSort(arr, low, pi - 1);  // Before pivot
        quickSort(arr, pi + 1, high); // After pivot
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output:

Original array: 10 7 8 9 1 5 
Sorted array: 1 5 7 8 9 10

Time Complexity:

Best Case O(n logn)
Average Case O(n logn)
Worst Case O(n²)

Space Complexity:

O(log n) – Due to recursive calls (not counting the input array, as it’s in-place).

Explanation:

partition() puts the pivot in the correct position and ensures all elements before it are smaller, and after it are larger.
Recursion is applied on both halves until base case is met.
Quick Sort is fast in practice and performs well on average, but not stable by default.

Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It builds a max heap, then repeatedly swaps the root (largest element) with the last element and reduces the heap size to sort the array.

Algorithm:

Build a max heap from the input data.
Swap the first (largest) element with the last element.
Reduce the heap size by one and heapify the root.
Repeat steps 2–3 until the heap size is 1.

C++ Code :

Run

#include<iostream>
using namespace std;

// To heapify a subtree rooted at index i
void heapify(int arr[], int n, int i) {
    int largest = i;         // Initialize largest as root
    int left = 2 * i + 1;    // left = 2*i + 1
    int right = 2 * i + 2;   // right = 2*i + 2

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);

        // Recursively heapify the affected subtree
        heapify(arr, n, largest);
    }
}

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

    // One by one extract elements from heap
    for (int i = n - 1; i >= 0; i--) {
        // Move current root to end
        swap(arr[0], arr[i]);

        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    heapSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output:

Original array: 12 11 13 5 6 7 
Sorted array: 5 6 7 11 12 13

Time Complexity:

Best Case O(n logn)
Average Case O(n logn)
Worst Case O(n logn)

Space Complexity:

O(1) – It sorts the array in-place using no extra space.

Explanation:

A max heap ensures that the largest element is at the root.
After placing the largest element at the end, the heap is reduced and re-heapified.
This continues until the heap is sorted.
It's not stable, but it’s very efficient and does not use recursion like Merge Sort.

Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that works by counting the number of occurrences of each element and using this information to place them in the correct position. It is efficient for sorting integers within a small, known range.

Algorithm:

Find the maximum element (say maxVal) in the array.
Create a count[] array of size maxVal+1 and initialize all values to 0.
Count the frequency of each element and store it in count[].
Update count[] so that each element at index i contains the sum of previous counts.
Build the output array by placing elements at their correct sorted position using the count[].
Copy the sorted elements back into the original array.

C++ Code :

Run

#include<iostream>
#include<vector>
using namespace std;

void countingSort(int arr[], int n) {
    // Find maximum element
    int maxVal = arr[0];
    for (int i = 1; i < n; i++)
        maxVal = max(maxVal, arr[i]);

    // Create count array and initialize to 0
    vector count(maxVal + 1, 0);

    // Count occurrences
    for (int i = 0; i < n; i++)
        count[arr[i]]++;

    // Update count[] so that each element is the sum of previous counts
    for (int i = 1; i <= maxVal; i++)
        count[i] += count[i - 1];

    // Output array
    vector output(n);

    // Build the output array (stable sort)
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // Copy back to original array
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    countingSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output:

Original array: 4 2 2 8 3 3 1 
Sorted array: 1 2 2 3 3 4 8

Time Complexity:

Best Case O(n + k)
Average Case O(n + k)
Worst Case O(n + k)

where n is the number of elements and k is the range of input.

Space Complexity:

O(k + n) – for the count array and output array.
⚠️ Limitation: Not suitable for negative numbers or large range of values.

Explanation:

The count[] array keeps track of how many times each number appears.
Then we compute prefix sums in count[] to determine the correct positions.
We then build the sorted array using this info.
It’s a stable sort and does not use comparisons.

Radix Sort

Radix Sort is a non-comparison-based sorting algorithm that sorts integers by processing individual digits. It sorts the numbers starting from the least significant digit (LSD) to the most significant digit (MSD) using a stable sorting algorithm like Counting Sort.

Algorithm:

Find the maximum number to know the number of digits.
Starting from the least significant digit, sort the array using Counting Sort.
Repeat the process for each digit position (units, tens, hundreds, etc.).
Since Counting Sort is stable, Radix Sort maintains the relative order.

C++ Code :

Run

#include<iostream>
#include<vector>
using namespace std;

// A utility function to get the maximum value in the array
int getMax(int arr[], int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) if (arr[i] > maxVal)
            maxVal = arr[i];
    return maxVal;
}

// A function to do counting sort based on a digit represented by exp
void countingSortByDigit(int arr[], int n, int exp) {
    vector output(n);
    int count[10] = {0};

    // Count occurrences of digits
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // Update count[i] so that count[i] now contains the actual position
    for (int i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array (stable sort) for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    // Copy the output array to arr[]
    for (int i = 0; i < n; i++) arr[i] = output[i]; } // Main Radix Sort function void radixSort(int arr[], int n) { int maxVal = getMax(arr, n); // Do counting sort for every digit for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSortByDigit(arr, n, exp);
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    radixSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output:

Original array: 170 45 75 90 802 24 2 66 
Sorted array: 2 24 45 66 75 90 170 802

Time Complexity:

Best Case O(n x k)
Average Case O(n x k)
Worst Case O(n x k)

Where n is the number of elements and k is the number of digits in the largest number.

Space Complexity:

O(n + k) – for the output array and count array used in Counting Sort.

Explanation:

Radix Sort sorts by digits, using Counting Sort as a subroutine.
It processes from right to left, ensuring stability.
It's fast for integers with a limited number of digits.
It does not work directly with negative numbers unless modified.

Bucket Sort

Bucket Sort is a distribution sort that divides the input into several buckets and then sorts each bucket individually (using another sorting algorithm, often Insertion Sort). Finally, it concatenates all sorted buckets.

Algorithm:

Create k empty buckets (usually based on the input range).
Distribute the elements into buckets based on a hashing or mapping function.
Sort each bucket individually (using Insertion Sort or any other efficient algorithm).
Concatenate all sorted buckets to get the final sorted array.

Best suited for uniformly distributed float numbers between 0 and 1, but it can be adapted for integers too.

C++ Code :

Run

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void bucketSort(float arr[], int n) {
    // Create n empty buckets
    vector buckets[n];

    // Put array elements in different buckets
    for (int i = 0; i < n; i++) {
        int index = n * arr[i]; // Index in the bucket
        buckets[index].push_back(arr[i]);
    }

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

    // Concatenate all buckets into arr[]
    int idx = 0;
    for (int i = 0; i < n; i++)
        for (float val : buckets[i])
            arr[idx++] = val;
}

void printArray(float arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    bucketSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output:

Original array: 0.897 0.565 0.656 0.1234 0.665 0.3434 
Sorted array: 0.1234 0.3434 0.565 0.656 0.665 0.897

Time Complexity:

Best Case O(n + k)
Average Case O(n + k)
Worst Case O(n²)

Where n = number of elements, k = number of buckets.

Space Complexity:

O(n + k) – Extra space for k buckets and the output array.

Explanation:

The array is split into buckets based on value distribution.
Each bucket is sorted individually.
The final sorted array is formed by combining all buckets.
It performs well on uniformly distributed data.

Applications of Sorting Methods in Data Structure

Sorting algorithms are used in a wide variety of applications:

Search Engines: Rank results based on relevance.
E-commerce: Filter and sort products by price, rating, or popularity.
Databases: Order records before merging or joining tables.
Data Analysis & Statistics: Sort large datasets to compute median, percentiles, etc.
Graphics: Z-index sorting in layered rendering.
Machine Learning: Preprocessing steps to clean and arrange data.
Operating Systems: Task scheduling, memory management.

Conclusion

Sorting is not just a textbook concept, it’s a real-world necessity. From basic apps to large-scale systems, sorting algorithms help keep data accessible, meaningful, and usable. By comparing their characteristics, knowing where each shines, and understanding their applications, you’ll be better equipped to solve any problem that involves organizing data.

Frequently Asked Questions

Why is Quick Sort faster in practice than Merge Sort, even though both have O(n log n) average-case time complexity?

Quick Sort is generally faster because:

It has better cache performance due to in-place sorting (no extra memory allocation like Merge Sort).
The inner loop of Quick Sort is tight and minimal, which makes it faster in practice.
Merge Sort always divides into equal halves, whereas Quick Sort’s partitioning can lead to better division depending on the pivot.

However, Quick Sort is not stable and can degrade to O(n²) if the pivot choice is poor.

Can a sorting algorithm be both in-place and stable? If yes, give examples. If not, explain why.

Yes, some algorithms can be both in-place and stable, but they are rare and usually not very efficient for large data.

Example: Insertion Sort is both in-place and stable.
But algorithms like Merge Sort (not in-place) and Heap Sort (not stable) show that achieving both simultaneously is often a trade-off.

Advanced optimized versions of Merge Sort can be made stable and almost in-place but are complex to implement.

What is the best sorting algorithm for nearly sorted data, and why?

Insertion Sort is best suited for nearly sorted data because:

It runs in O(n) time when the list is almost sorted.
It only shifts a few elements into place, making it highly efficient in such cases.

Other algorithms like Merge Sort or Quick Sort don’t take advantage of existing order and still run in O(n log n).

Why is Counting Sort not a comparison-based sorting algorithm, and what limitations does it have?

Counting Sort does not compare elements. Instead, it:

Counts the frequency of each unique element,
Uses those counts to place elements directly in the sorted position.

Limitations:

Only works well for integers within a small, known range.
It is not suitable for floating-point numbers, strings, or large ranges of input values due to high space usage.

How can you make Quick Sort stable and what challenges come with that?

Quick Sort is naturally unstable because swapping elements around the pivot can change the order of equal elements.

To make it stable:

You’d need to modify it to not swap equal elements indiscriminately or
Use additional data structures like index arrays to track positions.

Challenges:

The algorithm becomes more complex and memory-intensive.
It may lose the in-place advantage, making it slower in practice.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Unlock this article for Free, by logging in

Classification of Sorting Algorithms

Sorting Algorithms and its types

Table of Contents

What are Sorting Algorithms?

Uses and Importance of Data Structure Sorting

Prime Course Trailer

Related Banners

Classification of Sort Algorithms

1. Based on Number of Comparisons

2. Based on Recursion

3. Based on Stability

4. Based on Method of Sorting

Types of Sorting Algorithms in Data Structure

Characteristics of Sorting Algorithms

Bubble Sort

Algorithm:

C++ Code – Bubble Sort:

Output:

Selection Sort

Algorithm:

C++ Code :

Output:

Explanation:

Insertion Sort

Algorithm:

C++ Code :

Output:

Explanation:

Merge Sort

Algorithm:

C++ Code :

Output:

Quick Sort

Algorithm:

C++ Code :

Output:

Heap Sort

Algorithm:

C++ Code :

Output:

Counting Sort

Algorithm:

C++ Code :

Output:

Radix Sort

Algorithm:

C++ Code :

Output:

Bucket Sort

Algorithm:

C++ Code :

Output:

Applications of Sorting Methods in Data Structure

Conclusion

Frequently Asked Questions

Get over 200+ course One Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

30+ Companies are Hiring

Unlock this article for Free,
by logging in