Home/Blog/Interview Prep/Top 5 sorting algorithms every developer should know
Home/Blog/Interview Prep/Top 5 sorting algorithms every developer should know

Top 5 sorting algorithms every developer should know

13 min read
Dec 11, 2024

Sorting algorithms are fundamental to computer science and programming, playing a critical role in organizing data for efficient search, access, and manipulation. From dealing with large datasets to optimizing smaller applications, understanding how different sorting algorithms work can significantly enhance the problem-solving skills of any developer.

Think of sorting algorithms as the maestros of a symphony orchestra. Just as a conductor arranges musicians to create harmonious music, sorting algorithms arrange data to create order from chaos. When the data is perfectly sorted, everything runs smoothly, from the simplest searches to the most complex computations.

Sorting
Sorting

Having a strong grasp of sorting algorithms is neccesary for coding interviews and technical assessments. They are a core topic in most technical interviews, often used to evaluate a candidate’s understanding of algorithms and data structures.

In this blog, we’ll look into the top 5 sorting algorithms every developer should know:

  • Bubble sort

  • Heap sort

  • Insertion sort

  • Merge sort

  • Quicksort

We will cover bubble sort because it is fundamental for understanding basic sorting algorithms, even though it is less likely to appear in interview questions.

We’ll explore the unique characteristics, complexities, and practical applications of each algorithm, providing you with the knowledge to implement them. Let’s try to understand some important sorting algorithms.

Bubble sort#

Bubble sort is one of the simplest sorting algorithms. It works by repeatedly stepping through the list to be sorted, comparing adjacent items, and swapping them if they are in the wrong order. This process is repeated until the list is sorted.

Note: It’s called bubble sort because smaller elements bubble to the top or bottom of the list based on the comparison function.

Bubble sort is rarely used in practice due to its inefficiency with large datasets. However, it is useful for educational purposes and for understanding the basics of sorting algorithms. It finds its practical application in certain situations where the input is already nearly sorted or the list is small. In these cases, it performs relatively well because fewer passes are needed to sort the list.

Think of a real-time stock ticker displaying the top-performing stocks. When new stock prices are frequently updated, and the changes are usually minor, the list remains nearly sorted. In this case, bubble sort can maintain the sorted order by quickly integrating the minor updates.

Step-by-step walkthrough#

Performing bubble sort involves the following steps:

  1. Start at the beginning of the list.

  2. Compare the first two elements. If the first is greater than the second, swap them.

  3. Move to the next pair of elements, repeat the comparison, and swap if necessary.

  4. Continue this process until the end of the list. This completes one pass.

  5. Repeat the passes until no swaps are needed during a pass.

Let’s look at the illustration below to better understand the mechanism of bubble sort:

canvasAnimation-image
1 of 11

Complexity analysis#

One of the main factors in selecting a sorting algorithm is its performance in terms of time and space. Understanding these complexities helps in determining the algorithm’s efficiency and suitability for different applications:

Bubble sort

Best

Average

Worst

Reason

Time complexity

O(n)

O(n2)

O(n2)

The time complexity varies depending on whether the list is already sorted in random order or reverse order.

Space complexity

O(1)

O(1)

O(1)

It is an in-place sorting algorithmAn in-place sorting algorithm sorts the data by modifying the original input using a constant amount of extra memory (i.e., O(1) additional space). The algorithm rearranges the elements directly in the input array without needing to copy them to another data structure..

We will try to understand the bubble sort functionality with the help of a coding problem

Solving the student grades problem with bubble sort#

Problem: You are given an array of student grades for a recent exam. Your task is to write a program that uses bubble sort to sort these grades in ascending order.

Solution: We solve by iterating through the given list of grades, repeatedly comparing and swapping adjacent elements until the list is sorted:

def bubble_sort_grades(grades):
    n = len(grades)
    for i in range(n):
		# Flag for swapping
        swapped = False
        for j in range(0, n-i-1):
			# Comparing adjacent elements
            if grades[j] > grades[j+1]:
                # Swaping if they are in the wrong order
                grades[j], grades[j+1] = grades[j+1], grades[j]
                swapped = True
        
        if not swapped:
            break
    # Return the sorted list
    return grades
# Usage:
grades = [88, 75, 92, 85, 91, 78, 84]
print("Given Grades:", grades, "\n")
sorted_grades = bubble_sort_grades(grades)
print("Sorted Grades:", sorted_grades)

Bubble sort: a simplistic approach for educational use

Question

You are teaching a sorting algorithm to beginners and want to demonstrate how adjacent elements are swapped to sort a list.

Why is bubble sort often used for educational purposes despite its inefficiency?

Show Answer

Heap sort#

Heap sort is a sorting algorithm that uses a binary heap data structure. It operates by first constructing a heap from the input data and then repeatedly extracting the maximum element from the heap. The heap is then reconstructed, and this process continues until the entire array is sorted. This method ensures optimal performance and is particularly useful for large datasets. It’s often used in real-time systems and embedded systems due to its reliable time complexity.

Imagine organizing a bookshelf with books of varying heights. To sort them by height, you start by finding the tallest book and placing it at the end of the shelf. Then, you look for the next tallest book and place it before the previously placed tallest book. You repeat this process, always ensuring that the books already sorted are in the correct order. This is similar to how heap sort works by repeatedly extracting the maximum (or minimum) element from a heap and placing it in the correct position.

Step-by-step walkthrough#

Let’s review the steps included in this algorithm:

  1. Convert the given array into a max heap, where the parent node is always greater than its child nodes.

  2. Swap the root node with the last element in the heap.

  3. Reduce the heap size by one.

  4. Heapify the root element to restore the heap property.

  5. Repeat until the heap size is reduced to one.

Let’s look at the illustration below to better understand the mechanism of the heap sort:

canvasAnimation-image
1 of 7

Complexity analysis#

The time and space complexity analysis of this sorting algorithm is:

Heap sort

Best

Average

Worst

Reason

Time complexity

O(n log n)

O(n log n)

O(n log n)

Due to the properties of the binary heap.

Space complexity

O(1)

O(1)

O(1)

It is an in-place sorting algorithm.

Let’s try to understand the heap sort in more detail with the help of a coding problem.

Solving the deadline prioritization problem with heap sort #

Problem: You are given an array of project deadlines for various tasks. Your task is to write a program that uses heap sort to sort these deadlines in ascending order so you can prioritize tasks based on their deadlines.

Solution: Start by building a max heap from the given list of deadlines. Then, repeatedly extract the maximum element from the heap and place it at the end of the list, reducing the heap size each time. This ensures the list is sorted in ascending order:

def heapify(arr, n, i):
    # Initialize largest as root
    largest = i  
	# left and right child
    left = 2 * i + 1  
    right = 2 * i + 2  
    # Check if left child of root exists and is greater than root
    if left < n and arr[i] < arr[left]:
        largest = left
    # Check if right child of root exists and is greater than root
    if right < n and arr[largest] < arr[right]:
        largest = right
    # Change root if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap
        # Heapify the root
        heapify(arr, n, largest)
def heap_sort(arr):
    n = len(arr)
    # Build a maxheap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # One by one extract elements
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  
        heapify(arr, i, 0)
# Usage:
deadlines = [7, 2, 10, 4, 6]
print("Given deadlines:", deadlines, "\n")
heap_sort(deadlines)
print("Sorted deadlines:", deadlines)

Heap sort: consistent time and space for limited memory

Question

You are sorting a dataset where memory usage must remain constant and need consistent sorting performance.

When is heap sort a good choice?

Show Answer

Insertion sort#

It is a simple and efficient comparison-based sorting algorithm that builds the final sorted array one element at a time. It works by dividing the input array into a sorted and an unsorted section. At each step, it takes the first element from the unsorted section and inserts it into the correct position in the sorted section. This process repeats until the entire array is sorted.

Insertion sort is particularly useful when working with small datasets or nearly sorted data. It’s also often used as the final stage of more complex algorithms like quicksort or merge sort for small subarrays.

Imagine sorting a hand of playing cards. We pick up one card at a time and insert it into its correct position among the cards already in the hand. This ensures that the cards in our hand are always sorted.

Step-by-step walkthrough#

The algorithm works in the following manner:

  1. Begin with an unsorted array and consider the first element as sorted.

  2. Take the next element, compare it with the sorted element(s), and insert it into its correct position.

  3. Repeat the process for the remaining elements.

  4. At the end, the given array is sorted.

Insertion sort
Insertion sort

Complexity analysis#

Let’s have a look at the time and space complexity analysis of this sorting algorithm:

Insertion sort

Best

Average

Worst

Reason

Time complexity

O(n)

O(n2)

O(n2)

The time complexity varies depending on whether the list is already sorted in random order or reverse order.

Space complexity

O(1)

O(1)

O(1)

It is an in-place sorting algorithm.

We will understand the insertion sort functionality with the help of a coding problem.

Solving the book prices problem with insertion sort#

Problem: You are given an array of book prices in a store. Your task is to write a program that uses insertion sort to sort these prices in ascending order so the store can display them from the cheapest to the most expensive.

Solution: We solve by iterating through the given list of prices, repeatedly inserting each element into its correct position within the sorted portion of the array:

def insertion_sort(arr):
    # Traverse through 1 to length of array
    for i in range(1, len(arr)):
        key = arr[i]
        
        # Move elements of arr[0..i-1], that are greater than key,
        # to one position ahead of their current position
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
# Usage
prices = [29.99, 19.99, 24.99, 49.99, 9.99]
print("Given prices:", prices, "\n")
insertion_sort(prices)
print("Sorted prices:", prices)

Insertion sort: optimal for nearly sorted data

Question

You have a list of tasks sorted by priority, and new tasks are continuously added to it. The list remains mostly sorted with each addition.

Why is insertion sort ideal for this scenario?

Show Answer

Merge sort#

Merge sort is a highly efficient, stable, and comparison-based sorting algorithm that uses the divide-and-conquer technique. It works by dividing the unsorted list into smaller sublists until each sublist contains a single element. Then, it merges these sublists to produce new sorted sublists until there is only one sorted list remaining.

Merge sort is especially useful when working with large datasets or linked lists. It’s preferred in situations where a stable sort is required and when working with data structures that do not support random access, such as linked lists.

Suppose you are organizing a large group of people by height for a school photograph. First, you divide the group into pairs and determine the taller and shorter person in each pair. Then, you combine pairs into small groups, ensuring each group is sorted by height. You continue merging these groups, always maintaining order, until the entire group is sorted from shortest to tallest.

Step-by-step walkthrough#

Performing merge sort involves mainly three steps:

  1. Divide: Recursively divide the array into two halves until each sublist contains a single element.

  2. Conquer: Next, recursively sort these sublists.

  3. Combine: Merge the sorted sublists to produce new sorted sublists until there is only one sorted list.

Merge sort
Merge sort

Complexity analysis#

Let’s have a look at the time and space complexity analysis of this sorting algorithm:

Merge sort

Best

Average

Worst

Reason

Time complexity

O(n log n)

O(n log n)

O(n log n)

We consistently split (log n) the n halves.

Space complexity

O(n)

O(n)

O(n)

Additional space is required for the merging process.

Let's understand the merge sort algorithm with a practical coding problem.

Solving the athletes’ scores problem with merge sort#

Problem: You are given a list of athletes' scores from a recent competition. Your task is to write a program that uses merge sort to sort these scores in ascending order.

Solution: To solve this problem, we will implement the merge sort algorithm. It recursively splits the list into halves until each sublist contains a single element. Then, it merges these sublists back together in sorted order:

def merge_sort(arr, descending=False):
    if len(arr) > 1:
        
        # Find the middle point
        mid = len(arr) // 2  
        # Dividing the elements into 2 halves
        L = arr[:mid]        
        R = arr[mid:]
        # Sorting the first and second half
        merge_sort(L, descending)  
        merge_sort(R, descending)  
        i = j = k = 0
        # Save data in temp arrays L[] and R[]
        while i < len(L) and j < len(R):
            if (L[i] > R[j]) if descending else (L[i] < R[j]):
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        # Checking if any element was left
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
# Usage
scores = [90, 92, 78, 72, 88]
print("Given scores:", scores, "\n")
merge_sort(scores)
print("Sorted scores:", scores)

Merge sort: stable sorting for large files

Question

You need to sort a large dataset stored on a disk and ensure stability while sorting.

Why would merge sort be a good choice for sorting large files on disk?

Show Answer

Quicksort#

Quicksort is a highly efficient, comparison-based sorting algorithm that utilizes the divide-and-conquer approach. The algorithm selects a pivot element from the array and partitions the other elements into two subarrays based on whether they are less than or greater than the pivot. These subarrays are then sorted recursively, and this process continues until the entire array is sorted.

Note: Quicksort’s efficiency and performance make it a popular choice for handling large datasets.

It's often preferred in applications where average-case performance is critical. For example, quicksort is frequently used in the implementation of database query optimizers and in language libraries for sorting functions.

Suppose you are organizing a garage sale. You start by selecting an item (pivot) and then categorize all other items as either cheaper or more expensive than the pivot. You place cheaper items on one side and more expensive items on the other. You then take each group and repeat the process, further dividing them until every item is sorted by price.

Step-by-step walkthrough#

Performing quicksort involves mainly the following steps:

  1. Choose a pivot element from the array. Common strategies include choosing the first element, the last element, or a random element.

  2. Reorder the array so that all elements less than the pivot come before it and all elements greater than the pivot come after it.

  3. The pivot is now in its final position.

  4. Recursively apply the above steps to the subarrays of elements with smaller and greater values.

Quicksort
Quicksort

Complexity analysis#

Let's have a look at the time and space complexity analysis of this sorting algorithm:

Quicksort

Best

Average

Worst

Reason

Time complexity

O(n log n)

O(n log n)

O(n2)

The time complexity varies depending on which element is selected as the pivot.

Space complexity

O(log n)

O(log n)

O(log n)

Auxiliary space for recursive stack.

Let’s understand the quicksort functionality with the help of a coding problem.

Solving the temperature problem using the quicksort#

Problem: Given an array of temperatures recorded over a week. Your task is to write a program that uses quicksort to arrange these temperatures in ascending order, helping you easily identify the coldest and warmest days.

Solution: We select a pivot point, partition the array around the pivot, and recursively apply a quicksort to the subarrays:

def partition(arr, low, high):
    # pivot
    pivot = arr[high]  
    # index of smaller element
    i = low - 1  
    for j in range(low, high):
        if arr[j] <= pivot:
            i = i + 1
            # swap elements
            arr[i], arr[j] = arr[j], arr[i]  
    # swap the pivot
    arr[i + 1], arr[high] = arr[high], arr[i + 1]  
    return i + 1
def quick_sort(arr, low, high):
    if low < high:
        # pi is partitioning index
        pi = partition(arr, low, high)  
        # Recursively sort elements before and after partition
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)
# Usage
temperatures = [72, 68, 75, 70, 66, 74, 69]
print("Given temperatures:", temperatures, "\n")
quick_sort(temperatures, 0, len(temperatures) - 1)
print("Sorted temperatures:", temperatures)

Quicksort: efficient for large datasets

Question

You are handling a large dataset of millions of unsorted numbers and need to quickly sort them in memory with minimal overhead.

Why is quicksort suitable for large datasets, and when should you avoid it?

Show Answer

For those looking to dive deeper into data structures and algorithms, Educative offers a focused course that covers these concepts in real-world scenarios.

Cover
Data Structures for Coding Interviews in Java

Data structures are amongst the fundamentals of Computer Science and an important decision in every program. Consequently, they are also largely categorized as a vital benchmark of computer science knowledge when it comes to industry interviews. This course contains a detailed review of all the common data structures and provides implementation level details in Java to allow readers to become well equipped. Now with more code solutions, lessons, and illustrations than ever, this is the course for you!

35hrs
Beginner
65 Challenges
22 Quizzes

Next steps#

When choosing the right sorting algorithm, it’s important to take into account the dataset size, nature of the data, and specific requirements, such as time complexity, space complexity, and stabilityA sorting algorithm is stable if it preserves the relative order of elements with equal keys. This means that if two elements are equal, they will remain in the same relative positions as they were in the original input after sorting..

Additional resources#

We encourage you to experiment with these sorting techniques, apply them to various datasets, and analyze their performance. This hands-on approach will enhance your skills and help you determine the most effective algorithms for different scenarios.

Educative offers multiple resources to help you better understand algorithms and prepare for coding interviews. With practice and dedication, you’ll be well-equipped to tackle sorting problems optimally and confidently.

Frequently Asked Questions

What is the significance of sorting algorithms?

Sorting algorithms are essential for organizing data efficiently, making searching, accessing, and processing information in various applications easier.

Which sorting algorithms should every developer know?

What is the main difference between merge sort and quicksort?

Can sorting algorithms be used in real-time applications?

Written By:
Dian Us Suqlain
 
Join 2.5 million developers at
Explore the catalog

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

TRENDING TOPICS

Learn to Code

Tech Interview Prep

Generative AI

Data Science

Machine Learning

GitHub Students Scholarship

Early Access Courses

Blind 75

Layoffs

Pricing

For Individuals

Try for Free

Gift a Subscription

CONTRIBUTE

Become an Author

Become an Affiliate

Earn Referral Credits

RESOURCES

Blog

Cheatsheets

Webinars

Answers

ABOUT US

Our Team

Careers

Hiring

Frequently Asked Questions

Contact Us

Press

LEGAL

Privacy Policy

Cookie Policy

Terms of Service

Business Terms of Service

Data Processing Agreement

INTERVIEW PREP COURSES

Grokking the Modern System Design Interview

Grokking the Product Architecture Design Interview

Grokking the Coding Interview Patterns

Machine Learning System Design

Tiktok Streamline Icon: https://streamlinehq.com

Copyright ©2024 Educative, Inc. All rights reserved.

soc2