#sortingalgorithms

Seminar on Sorting Out the Future - SIRT Bhopal

Join us for an insightful seminar on “Sorting in Data Structures” with expert “Mr. Pradeep Mishra”, Tech Lead, Virtusa!

Organized by the Department of AIML and CSECS, this session promises to dive deep into the world of data structures and algorithms.

Date: 10th September, 2025 Time: 9:30 - 12:00 PM

Quicksort is a very elegant nlogn sorting algorithm. It involves recursively partitioning the array on either side of a “pivot” element such that all elements before the pivot are smaller than the pivot, and all elements after the pivot are larger than the pivot. Doing this repeatedly on each partition sorts the array.

1. Choose a pivot. For starters let’s just choose the last element in the array.

2. Partition the array so that smaller-than-pivot elements are to the left of the pivot, and larger elements are to the right.

Starting at the left, we will have 2 counters, one to tell us the index of the last swap, i, and one for the current index, j. Both are initialized to 0. 

We will now traverse the array by incrementing j. If the element at j is larger than the pivot, skip it -- this will cause it to fall into the right side partition by default. Increment j. 

If arr[j] is smaller than the pivot, that’s one we want in the left partition! How do we get it there? We will swap it with the element at i, which indicates the index of the last swap (plus one), and therefore guarantees all elements before it are smaller than the pivot. Once we’ve swapped, we increment i since the index of the last swap has changed, and we continue incrementing j to keep checking the remaining elements.

Once j reaches the element before the pivot, we are done with the first partition: elements before i are smaller than the pivot, and elements after i are larger than it. Now we just need to put our pivot in between those, and it will be in its ‘rightful position’ in the final array. To do this, we swap the pivot with the element at i. 

3. Recursively sort the partitions we just created. Remember, the pivot does not need to be included because it is already in the correct place! 

I realized the code I wrote for this is on my other computer, and I’m feeling lazy, so I will add that to this post later.

Here’s the YouTube explanation that I found to be the most helpful: 

Merge sort is a method of sorting an array in O(n*log(n)) time.

Start with an array: [5, 2, 4, 1, 3]

Break it in half (roughly).

Right half: [5, 2, 4]

Left half: [1, 3]

Do it again for each half.

Left half’s right half: [5, 4]

Left half’s left half: [2]

------------------------

Right half’s left half: [1]

Right half’s right half: [3]

Once more for the one that isn’t a single element yet: Break [5, 4] into [5] and [4].

These single-element arrays are sorted already. That’s our base case! Now to output a full array that’s sorted we start recombining the single-element arrays in a specific way. The deepest level of recursion we reached was with [5] and [4] (3 levels deep because we broke in half 3 times before we reached single-element arrays). So we start there when we begin working our way back up. How do we merge [5] and [4] into a sorted array? We read and compare the elements in each array, one by one. In this case the first and only elements in question are 5 and 4. Since 5 is more than 4, we add 4 to our result array: merged = [4]. Then since we’re done with it, we remove it from the array it came from. Now we are comparing the arrays [5] and []. Since one array is completely empty, and the other one is guaranteed to be sorted, we can just tack on the remaining array to our merged array to get: merged = [4, 5]. By the same logic, [1] and [3] recombine one level up into [1, 3]. So far all very trivial.

Now, we move one level up again: how do we combine [4, 5] with [2]? 

As before, we will compare the elements of each array, one by one. Up first: 4 and 2. 2 is smaller, so add 2 to the resulting array for this step: merged = [2]. Also, remove it from the array it came from (that is, from the subproblem of sorting [2], which of course returned [2]). Now we are comparing [4, 5] and []. Again, we have completely finished with one of the arrays, so we tack on all the leftover array to the resulting array: merged = [2, 4, 5].

By similar logic, we can combine the [1] and [3] from the right half of the original array to get [1, 3]. That leaves us with the final step of combining [2, 4, 5] with [1, 3]. Going through the arrays element by element, the first values in question are 2 and 1. 1 is smaller so we add 1 to the result for this step: merged = [1]. (Notice how since we are in a different stack frame for each of these subproblems we start with a fresh value for merged every time.) We remove 1 from its place in [1, 3] so the remaining comparisons will be between [2, 4, 5] and [3]. Up first: 2 vs 3. 2 is smaller so we move it from its current place to the final array: [2, 4, 5] becomes [4, 5] and merged becomes [1, 2]. Comparing [4, 5] and [3], we first check 4 vs 3. 3 is smaller so we move it to the result: merged = [1, 2, 3] and the remaining arrays are [4, 5] and []. As before, when one of the arrays becomes empty, we can safely tack on the remaining array to the result for a fully sorted solution: merged = [1, 2, 3, 4, 5]. Nice job!

Here is an example implementation of the process we just described in Ruby:

En este post vamos a terminar con los algoritmos de ordenación. En concreto, contaremos qué vamos a usar para probarlos y luego haremos unas correcciones de algunos de ellos.