Sorting algorithms explained, compared – Musings by FlyingSalmon

In this post, I discuss some common sorting algorithms, their logic, share their implementation (code), and demonstrate each one with executable scripts. Then I compare their performances to identify the most efficient sorting algorithm(s). You’ll get a good overview of each one, learn how to code and use them, and understand their strengths and weaknesses.

Let’s discuss Bubble sort, Insertion sort, Binary Insertion sort, and Timsort algorithms one by one.

Bubble Sort

Bubble sort sorts items by repeatedly comparing and swapping them. Here’s a simple analogy:

Imagine you have a line of kids arranged by height, but they are all jumbled up. You want to arrange them from shortest to tallest.

First Pass: You start at one end and compare the first two kids. If the first kid is taller than the second, you swap them so the shorter one is in front. Then you move to the next pair and repeat this process until you reach the end of the line. At this point, the tallest kid will have “bubbled up” to the last position.
Subsequent Passes: You go back to the start and repeat the process. Each pass through the line moves the next tallest kid to their correct position.
Continue Until Sorted: You keep doing this until there are no more swaps needed, meaning the line of kids is sorted from shortest to tallest.

Here’s a visual example with numbers:

Initial list: [5, 3, 8, 4, 2]

First pass:

Compare 5 and 3: Swap (3, 5, 8, 4, 2)
Compare 5 and 8: No swap (3, 5, 8, 4, 2)
Compare 8 and 4: Swap (3, 5, 4, 8, 2)
Compare 8 and 2: Swap (3, 5, 4, 2, 8)

Second pass:

Compare 3 and 5: No swap (3, 5, 4, 2, 8)
Compare 5 and 4: Swap (3, 4, 5, 2, 8)
Compare 5 and 2: Swap (3, 4, 2, 5, 8)

Third pass:

Compare 3 and 4: No swap (3, 4, 2, 5, 8)
Compare 4 and 2: Swap (3, 2, 4, 5, 8)

Fourth pass:

Compare 3 and 2: Swap (2, 3, 4, 5, 8)

List is now sorted: [2, 3, 4, 5, 8]

Bubble sort is simple and intuitive, but it isn’t the most efficient for large lists. It’s mostly used for educational purposes or when dealing with small sets of data.

Run the sorting algorithm by clicking on on the widget below. You can also modify the code on the left pane (such as adding more numbers in the list to sort) and click Run again to run your edits (you must know some Python syntax in order to operate it properly). The output on the right pane will show the state of the list of numbers after each step so you can follow along.

Insertion Sort

Imagine you’re sorting a deck of cards in your hand. You pick up each card one by one and place it in its correct position among the cards you’ve already sorted.
That’s basically what insertion sort does.

Here’s a step-by-step explanation:

Start with the first card: Assume the first card is already sorted.
Pick the next card: For each new card, compare it with the cards you’ve already sorted, starting from the rightmost (latest) sorted card.
Find the correct position: Shift the sorted cards one position to the right until you find the right spot for the new card.
Insert the card: Place the new card in its correct position.
Repeat: Continue this process for each card until all cards are sorted.

Here’s a visual example with numbers:

Initial list: [8, 15, 7, 5]

First card: (8) [already sorted]

Second card (15):

Compare 15 with 8: 15 is greater, so it stays in place.
Sorted list: [8, 15]

Third card (7):

Compare 7 with 15: 7 is smaller, so shift 15 one position to the right.
Compare 7 with 8: 7 is smaller, so shift 8 one position to the right.
Place 7 in its correct position.
Sorted list: [7, 8, 15]

Fourth card (5):

Compare 5 with 15: 5 is smaller, so shift 15 one position to the right.
Compare 5 with 8: 5 is smaller, so shift 8 one position to the right.
Compare 5 with 7: 5 is smaller, so shift 7 one position to the right.
Place 5 in its correct position.
Sorted list: [5, 7, 8, 15]

By the end, the list is sorted: [5, 7, 8, 15]

Insertion sort is simple and works well for small lists or nearly sorted lists. However, it can be inefficient for large, unsorted lists.

Run the sorting algorithm by clicking on on the widget below. You can also modify the code on the left pane (such as adding more numbers in the list to sort) and click Run again to run your edits (you must know some Python syntax in order to operate it properly).The output on the right pane will show the state of the list of numbers after each step so you can follow along.

Binary Insertion Sort

Binary insertion sort is a more efficient version of the insertion sort algorithm. Here’s an example:

Imagine you’re organizing a deck of cards in your hand. As you pick up each card, you want to place it in its correct position among the cards you’ve already sorted.
Instead of just scanning through the sorted cards one by one, you use a more efficient approach called binary search to find the correct position.

Here’s how it works:

Start with one card: Assume the first card is already sorted.

Pick the next card: For each new card, use binary search to find its correct position in the already sorted section of the deck.

Binary search divides the sorted section in half to determine whether the new card should go in the left or right half.
Repeat this process on the appropriate half until you find the exact position for the new card.

Insert the card: Once you know where the new card belongs, shift all the cards after it to the right to make space, then insert the new card into its correct position.

Repeat: Continue this process for each new card until all cards are sorted.

Here’s a visual example with numbers:

Initial list: [5, 3, 8, 4, 2]

First card: (5) [assume first one is already sorted]

Second card (3):

Binary search in [5]: 3 should go before (left of) 5.
Insert 3: [3, 5]

Third card (8):

Binary search in [3, 5]: 8 should go after (right of) 5.
Insert 8: [3, 5, 8]

Fourth card (4):

Binary search in [3, 5, 8]: 4 should go between 3 and 5.
Insert 4: [3, 4, 5, 8]

Fifth card (2):

Binary search in [3, 4, 5, 8]: 2 should go before 3.
Insert 2: [2, 3, 4, 5, 8]

List is now sorted: [2, 3, 4, 5, 8]

Binary insertion sort improves the efficiency of the regular insertion sort by using binary search to find the correct position, making it faster for large lists.

Timsort

Timsort can be explained in these simple terms:

Timsort starts by identifying small segments or chunks of data in the array that are already ordered (either ascending or descending). These chunks are called “runs.”
It might also reverse some segments to make them ordered correctly.
For small runs, Timsort uses insertion sort, which is very efficient for small or nearly sorted datasets. It ensures each segment is completely sorted.
Once the small runs are sorted, Timsort then uses a technique similar to merge sort to merge these runs together into larger sorted sequences.

Performance Comparison

The executing time of each of the sorting algorithms are were measured and averaged using the exact list of 50 numeric items. The times taken by each are shown in milliseconds in the chart below. It’s clear that despite 5101 milliseconds is about 5 seconds, the Bubble sort algorithm was the slowest of them all, while Timsort was incredibly fast taking just 0.0013 milliseconds (1.253E-06 seconds)! Binary Insertion sort was the second most efficient taking just 155 milliseconds (0.155 seconds).

I hope you found this post helpful and interesting. Explore this site for more tips and articles. Be sure to also check out my Patreon site where you can find more free downloads and optional fee-based code and documentation. Thanks for visiting!