I have been writing vanilla Javascript for a week and have used many operators and methods, one of which was Array#sort().
For those who are unfamiliar with the method, the sort method reorganizes the array based on conditions.
For an array of simple numbers, it looks like this:
// myArray = [1,5,7,2,8,9,4]
myArray.sort();
console.log(myArray)
// expected output: Array [1,2,4,5,7,8,9]Sort can also work on strings:
// myArray = ['Aaron', 'Zebra', 'Bill', 'Jon', 'Frank']
myArray.sort();
console.log(myArray)
// expected output: Array ['Aaron', 'Bill', 'Frank', 'Jon', 'Zebra']Essentially what’s happening under the hood is that the sort function goes through each value inside the array, compares the first value “a” with the second value “b.”
If the difference between a and b is a negative number or 0, it does not change the sorting and moves onto the next set. If the difference between a and b is a positive number, the sort function inverts the position of the two and moves on.
It repeats this iteration until the difference between a and b of the entire set is a negative number or 0, confirming that it has been sorted in an ascending order.
The strings are no exception to this rule; they have their own intrinsic values that the sort function goes through case by case, set by set. It is because of this rule that this happens when you compare a string that starts with lower case and one that starts with an upper case:
// myArray = ['aaron', 'Zebra', 'bill', 'Jon', 'Frank']
myArray.sort();
console.log(myArray)
// expected output: Array ['Frank', 'Jon', 'Zebra', 'aaron', 'bill']This is because the value of lower case letters are actually higher than that of upper case letters. Thus, the rules of finding the difference between a and b then sorting based on the computational output still applies.
This makes sense but what’s actually happening? What kind of algorithm does the sort function consist of?
I pursued this rabbit hole and found some interesting information (but not necessarily a single answer for all sort functions).
Upon further digging, I found out that the sort function actually employs different commands based on the browser you’re using, the amount of data you wish to sort, and the values inside the array. This is done to find the most optimal way of sorting the dataset you wish to sort, which impacts the sorting performance of the algorithms.
Quicksort
Google Chrome and Safari use variations of quicksort for numeric arrays(arrays of primitive type). This variation of quick sort is the C++ standard library function known as std::qsort also known as introsort.
Visually, this is what quicksort looks like:
Quicksort is a divide and conquer algorithm that defines elements inside the array then recursively sort through the sub-arrays. The steps it takes are:
- Pick an element called pivot from the array.
- Reorder the array so that elements with values less than the pivot come before the pivot and any elements greater than the pivot come after. This is called the partition operation.
- Recursively apply the first two steps to the sub-array of elements with smaller values and separately to the sub-arrays of elements with greater value.
The pivot selection and partition operation can be done in several different ways in which the choice of specific implementation schemes greatly affects the algorithm’s performance.
Merge Sort
When the arrays are non-numeric, the values inside the array are stringified then is sorted through merge sort(Mozilla/Firefox also resorts to merge sort by default). Here is a slow(but self-explanatory!) representation of merge sort:
For actual algorithmic visualization with graphical dots, it can be represented this way:
Here are the steps merge sort takes:
- Divide the unsorted list into n sublists, each containing 1 element.
- Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This last remaining sublist will be the sorted list.
The merge sort is an efficient, general-purpose sorting algorithm that accomplishes its job well when it comes to comparison.
Selection Sort
For any other types of arrays, selection sort is used:
As written in the Wikipedia page, selection sort divides the input list into two parts: the sublist of items already sorted(which starts out empty), and the sublist of items remaining to be sorted that occupy the rest of the list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, swapping it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
This explanation can be visualized with this snippet:
Sorted sublist == ( )
Unsorted sublist == (11, 25, 12, 22, 64)
Least element in unsorted list == 11
Sorted sublist == (11)
Unsorted sublist == (25, 12, 22, 64)
Least element in unsorted list == 12
Sorted sublist == (11, 12)
Unsorted sublist == (25, 22, 64)
Least element in unsorted list == 22
Sorted sublist == (11, 12, 22)
Unsorted sublist == (25, 64)
Least element in unsorted list == 25
Sorted sublist == (11, 12, 22, 25)
Unsorted sublist == (64)
Least element in unsorted list == 64
Sorted sublist == (11, 12, 22, 25, 64)
Unsorted sublist == ( )Source: https://en.wikipedia.org/wiki/Selection_sort
As you may have guessed, this has O(n²)time complexity, meaning that it is a fairly inefficient method of sorting compared to its sorting brothers such as merge sort, quick sort, etc.
Ultimately, different sort methods are used based on the browser you are using and the type/amount of values you are sorting. As the amount of data you want to sort becomes greater, the performance levels of each sort methods become important as to not have the elementary algorithm take too long to perform its functions.
