The Research Nest
Published in

The Research Nest

Understanding sorting: A super-simplified explanation

Python and javascript implementations for algorithms

So, why do you need to logically understand how those sort functions work?

In some interviews, you may be asked to explain it or solve for something without using the inbuilt functions. So, it is necessary to have a basic understanding of the same.

Problem Statement

The solution

  • First, let us think of something straightforward. If we have an array of numbers, we need to reassemble it so that the numbers are arranged in ascending order. Whenever there is an array to deal with, the first obvious thing that can be done is to write a for loop to visit each element of the array.
  • Let me take a sample array and try to construct logic by doing a dry run. Assume you have an array = [5, 7, 3, 2].
  • You can easily tell that the sorted array is [2, 3, 5, 7]. As humans, we simply look at numbers and rearrange them. How do we make a computer understand that?
  • One direct observation you can notice is that in a sorted array, all the elements to the left of any given element are lesser than that element and those to the right are greater than that element.
  • We just need to ensure the same for all elements. Numbers to the right of any given element must be greater than that number.
  • Let me do a dry run on [5, 7, 3, 2]. Let us visit the first element 5. 7 > 5 and is to the right of 5. Logically correct. Let us now go to the element 7. The next element 3 is less than 7. Hence it should be pushed to the left of 7. This can be done by swapping the positions. Our new array would now be [5, 3, 7, 2].
  • Similarly 2 < 7. So we swap again to get [5, 3, 2, 7] after running this logic across the array once. Notice that 7 is now in the correct position.
  • Loop once more with the same logic and you will get [3, 2, 5, 7]. Do it once again, and you’ll get the required answer = [2, 3, 5, 7].
  • What we did just now is like the bubble sort. It’s a brute force approach to sorting. As you can see, we are looping through the array multiple times.
  • The direct way we can find this is by creating a combined array of nums1 and nums2 of length m + n. Then we sort this array and find the median using the standard formula.
  • Python has another inbuilt function called sorted() which can be used to sort strings in order of the alphabet.
  • If given strings are anagrams, then the sorted strings will be equal. That’s the logic we can use.
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)
  • So, we have an array of n integers from [0, n] with one number missing.
  • If we sort this array, the ith number will be in the ith index, except for when we reach the missing number.
  • Let’s take an example array [4, 0, 1, 2]. We have n = 4.
  • Sort this array and you get [0, 1, 2, 4].
  • Here, we can see that array[0] = 0, array[1] = 1, array[2] = 2.
  • But array[3] != 3, and its value is 4. Hence, 3 is the missing number.
  • If we loop through the entire array and find that all numbers are equal to their index, then the missing number will be the final number, the length of the array itself.
var missingNumber = function(nums) {
const n = nums.length
return ( n*(n+1)/2 - nums.reduce(function(a, b) { return a + b;}, 0));

How do you sort a billion files efficiently?

Beyond the online tests and DSA rounds, this is a common interview question you may come across. When given a huge amount of data, we can’t do things normally. There are some approaches that can be used to optimize stuff.

How exactly is this external memory used?

Among the many ways to do it, there are two standard ways called external merge sort and external distribution sort.



Empowering humanity with exclusive insights.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store

Tech 👨‍💻 | Life 🌱 | Careers 👔 | Poetry 🖊️