Sort Algorithms

Recently, I worked on a sort visualizer project that displays various sorting algorithms and I will be talking about some of the algorithms I used.

So, what’s a sort algorithm?

A sort algorithm is used to arrange a given array or list of elements in a specific order.

The algorithms I will go over are:

• merge sort
• quick sort
• bubble sort
• tim sort
• heap sort

Merge Sort

• divides an array into smaller subarrays, sorts each subarray and then merges the sorted subarrays back together to form the final sorted array.

Let’s take an example:

QuickSort

• Similar to merge sort, quickSort is also a divide and conquer algorithm. It selects a ‘pivot’ element from the array and partitions the array around the ‘pivot’ element. There are several methods of picking the ‘pivot’ element. You can select the first element, last element, random element, or even the median.

Bubble sort

• The simplest sorting algorithm that works by repeatedly comparing two adjacent elements and swapping them if they are not in order.

TimSort

• TimSort is a sorting algorithm adapted from merge sort and insertion sort. The array is broken down into runs. The size of the run varies from 32 to 64 depending on the array size. The merge function performs well when size subarrays are powers of 2. Each run is sorted using insertion sort. Any array with a size smaller than 64 is sorted just using insertion sort. All runs are then merged one by one using merge sort.
• A fun fact about timSort is that it is used in Java’s Array.sort() as well as Python’s sorted() and sort()

In this example, the size of the run is 4.

Heap sort

• Heap Sort sorts an array by building a binary heap data structure from the elements of the array and then repeatedly extracting the maximum element from the heap and moving that to the end of the array, reducing the size of the heap by one each time until the heap is empty.

Conclusion

There are many sorting algorithms out there and we didn’t even cover non-comparison-based sorting algorithms. In this article, we went over several comparison-based sorting algorithms with bubble sort being the most inefficient and quickSort and timSort being the most efficient. I hope this gave you a better understanding and a visual of how sorting algorithms operate.

You can check out my project here

Github repo

Thanks for reading!