fbpx

Zakaria Loai is a Social Hackers Academy graduate from the Career Track for Full-Stack Web Development in Class 17. Following his work, we find very interesting and valuable articles on his Medium profile discussing diverse topics in Full-Stack Development. One of these is the following article about the 2 Methods of Fast Sorting Algorithms.

The first part

Merge sort depends on splitting the big problem into smaller problems. So it will be an easier problem to solve because splitting the big problem weakens its complexity.

Imagine that you have an array of 16 elements and want to sort them. If you deal with the 16 elements at once, it will be more difficult, but what if I divide it into 2 arrays and sort each array alone the difficulty decreases by half as I will only deal with 8 elements.

And what if I divided each array of 8 elements into two arrays each one having 4 elements the difficulty will keep decreasing, as shown in the image below. If we keep dividing the array we end up with an array of 1 element and the problem converted from sorting 16 elements to sorting 2 elements only.

After sorting the 2 elements only, we will climb the tree recursively with an array sorted in ascending order, and then when comparing the two arrays that have bigger lengths, it will be easier because we have already granted that both arrays we compared are sorted.

As the final step, we will have two big arrays containing the elements of the original array and each of them is sorted that will make our mission easier as if the first element in the left array is smaller than the first element in the right array then it is the smallest one in both of them and we guarantee that we put it in the right spot.

To make our code cleaner and less complex we will make a standalone function that is responsible for merging two sorted arrays into one array and call it mergeArrays:

To make our code cleaner and less complex we will make a standalone function that is responsible for merging two sorted arrays into one array and call it mergeArrays:

Then, we will start implementing a mergeSort function that will make use of:

  • Itself in dividing the original array into smaller arrays (recursion).
  • The mergeArrays function to sort the divided arrays.

Explain how does mergeSort function works with an example in the below image:

Is this algorithm more efficient than the insertion sorting algorithm?

Yes, it’s much more efficient In half a second (500 ms) of computation time, Sorting by insertion can sort sequences of length up to 8,000, whereas Mergesort manages 20 times as many numbers simultaneously.

Why it’s more efficient?

Because as we mentioned before the insertion sort algorithm time complexity is O(n²) but the time complexity for merge sort is O(n log₂(n)) and that’s because if we have an array of 16 elements it will be decomposed in 4 levels (log₂(16) = 4) and If we calculate the total of comparisons in each decomposition we will find it equal to n so we get O(n log₂(n)).

The Second Part

The quick sort algorithm has the same time complexity as the merge sort and in some cases, it might be worse in time complexity than the merge sort.

Of course, now you wonder why I even do quick sort if it might be worse than merge sort which is more consistent and has constant time complexity in all cases well It depends on the type of data structure you sorted and how much it’s already sorted.

In terms of how much data is already sorted or nearly sorted The worst case of the quick sort has a time complexity of O(n²) but a merge sort will still have the same time complexity of O(n log₂(n)) so merge sort in this case is better.

In terms of your data structure type, If you are sorting an array, it will be better to use quick sort as it doesn’t require extra storage as merge sort, which has a space complexity of O(n) when it is used to sort an array and that may be quite expensive and it increases the time needed to sort the array so as conclusion quick sort is better in sorting arrays but merge sort is good in sorting linked-lists as it space complexity will be O(1) instead of O(n).

To implement quick sort we need a swap function, pivot function and finally the quick sort algorithm function itself. Let’s start with the swap function which all it does is swap two elements inside the array and it’s used by the pivot function.

The pivot function returns the right spot for the element you pass to it. Choosing the right pivot improves the efficiency of this algorithm if you can detect the median value inside the array then it will be the perfect pivot to start with but in our case, we will consider the pivot as the first element in the array.

The image below contains an example of how the pivot function runs and shows that the main mission of this function is to put a number in its right spot how?

By ensuring that every element that comes before the pivot is less than the pivot and every element comes after the pivot is bigger than the pivot.

The quick sort algorithm is a recursive function which uses a pivot to arrange the left and right sides of it and below is the implementation of it.

How does it work the below image contains an example of how the quick sort function works that makes it clear how things are done behind the scenes.

Want to learn Full-Stack Web Development?

Social Hackers Academy is the right place for you to become a full-stack web developer in a 7-month period, followed by intense and peer learning, working in a team on real-world projects and being mentored by world-class instructors. Want to learn more about becoming a web developer with Social Hackers Academy? Follow this page and book a call with our admission team.