The Sorting Algorithm Cup: Round 2

Join us for the second round of the Sorting Algorithm Cup. Today we will see Gnome Sort, Heap Sort, Insertion Sort and Merge Sort.

Bracket for the Competition

Ladies and gentlemen, tech enthusiasts and code connoisseurs, welcome back to The Sorting Algorithm Cup! In this thrilling second round, we have another four incredible algorithms ready to battle it out for sorting supremacy. Who will emerge victorious and secure a spot in the grand finale? Let’s find out!

In this round, our contenders are Gnome Sort, Heap Sort, Insertion Sort, and the infamous Merge Sort. Let’s meet our competitors!

Contestant #1: Gnome Sort

First up, we have the quirky and unconventional Gnome Sort! Gnome Sort is simple yet effective for small datasets, falling a bit short on the bigger ones… If a number is out of order, the algorithm swaps it with the previous number and goes back and checks again. This continues until the algorithm reaches the end of the list.

• Time Complexity: O(n²)

How it Works:

1. Start at the beginning of the list
2. If the current element is in the correct order relative to the previous element, move one step forward.
3. If it’s not, swap the current element with the previous element and move on step back.
4. Repeat steps 2 and 3 until the list is sorted.

Watch it in Action:

Gnome Sort sorting a list of 100 numbers from 0–99

Contestant #2: Heap Sort

Next, bringing a touch of mathematical elegance, is Heap Sort! This algorithm uses a binary heap data structure to sort elements efficiently. By builing a max heap, Heap Sort ensures that the largest element is at the root of the heap, which is then swapped with the last element of the list. The heap is then rebuilt, and the process continues until the list is sorted. Heap Sort is known for its consistent performance and is often used in systems where reliability is key.

• Time Complexity: O(n log n)

How it Works:

1. Build a max heap from the input data.
2. Swap the root of the heap with the last element of the heap.
3. Reduce the heap size by one and heapify the root.
4. Repeat steps 2 and 3 until the heap size is reduced to 1.

Watch it in Action:

Heap Sort sorting a list of 100 numbers from 0–99

Contestant #3: Insertion Sort

Our third contender is the meticulous and reliable Insertion Sort. This algorithm works similarly to how you might sort playing cards in your hands. It builds the sorted list one element at a time, inserting each new element into its proper place among the previously sorted elements. Although it’s not the fastest for large datasets, Insertion Sort shines with its simplicity and efficiency for small or nested datasets.

• Time Complexity: O(n²)

How it Works:

1. Start with the second element of the list.
2. Compare it with the elements before it and insert it into the correct position.
3. Move to the next element and repeat step 2 until the list is sorted.

Watch it in Action:

Insertion Sort sorting a list of 100 numbers from 0–99

Contestant #4: Merge Sort

Last but definitely not least, we have the powerful and efficient Merge Sort. This algorithm employs the divide-and-conquer strategy to sort the list. It divides the list into smaller sublists until each sublists contains only one element. Then, it merges these sublists to produce new sorted sublists until there is only one sorted list. Merge Sort is known for its reliable performance and is often used for large datasets.

• Time Complexity: O(n log n)

How it Works:

1. Divide the list into two halves.
2. Recursively divide each half until each sublist contains only one element.
3. Merge the sublists to produce sorted sublists until only one sorted list remains.

Watch it in Action:

Merge Sort sorting a list of 100 numbers from 0–99

And They’re Off!

I have used the same 1000 element shuffled list as I did in the last article. Our contestants have raced against each other to sort this array and here are the results:

Drumroll, please

Here’s how each algorithm performed based on 5 repeats:

time taken for each algorithm to sort the same list in seconds

Where the range represents the consistency of the algorithm by showing the difference between the highest and lowest times, the smaller it is, the more consistent.

AAAnd the winner of round 2 is officially Merge Sort, achieving a mean time of 0.002696 seconds. Congratulations to Merge Sort on moving to the grand finale to compete against the winners of our upcoming races.

Stay Tuned

That’s all for today’s race, folks! Stay tuned for the next round where the following algorithms will battle it out for a spot at the grand finale:

• Odd-Even Sort
• Pancake Sort
• Quick Sort
• Tim Sort

This will be a massive round with the giants Quick Sort and Tim Sort so make sure you check it out tomorrow! Don’t forget to share your thoughts and predictions in the comments below. Until next time…

If you want the code for any of these projects, I have it in my GitHub:

GitHub - batuSenturk/Sorting-Algorithms

Feel free to ask any questions. Let’s keep this conversation going!

Hi, I’m Batu. I write about Computer Science topics and explain different algorithms to give you potential project ideas. For my stories to pop up on your feed, I’d love for you to follow me (Batu Senturk).