Array Sort in JavaScript
FREE
Overview
The sort() method converts the elements of the input array into strings, and then the elements are compared according to their sequences of UTF-16 code units values.
Note: By default, the arrays are sorted in ascending order.
Introduction
The sort() method is used to sort arrays in javascript. The array sort in javascript uses in-place algorithm to sort array in javascript, i.e. the input array is transformed into a sorted array without using any auxiliary data structure. The input is usually overwritten by the output as the algorithm executes.
Syntax of Array Sort in JavaScript
The arr is the array that need to be sorted.
The array sort method in javascript can be called with or without any parameter.
When the array sort is called without any parameter, by default, it sort array javascript in increasing order.
Parameters of Array Sort in JavaScript
- compFunc
This is a function. This is passed as parameter in Array sort function to define the sorting behavior of the array sort. For e.g. we can pass the function such that the array sort happens in decreasing order.
Note: The compFunc is an optional parameter in array sort.
compFunc is discussed in detail in the upcoming section of the article.
In this article, we will be using different syntax for the compareFunction declaration in different examples to get an even broader scope.
-
x: This defines the starting index of the array from where the array sort should start.
-
y: This is the last index of the array till where the array sort should happen.
Return value of Array Sort in JavaScript
The array sort method sorts the input array. The sorting operation happens on the same array and no new array is created.
The sorting of the array happens by using the in-place algorithm, i.e. by transforming the input using no auxiliary data structure.
Time complexity of Array Sort in JavaScript
The time complexity of the sort cannot be guaranteed as it depends on the implementation.
The firefox web browser uses the merge sort implementation and its time complexity is O(nlog n).
The chrome web browser uses the Timsort implementation, which is a hybrid of merge sort and insertion sort, and its time complexity is O(nlogn) (while in the case of a small array, its time complexity is `O(n)``).
Sorting an Array in Javascript
Before we sort an array, let's create an array and display its elements.
Creating an array
Let's create an array of the first five multiples of 5. We'll create this array by the array literal method.
Now, we have an array arr that contains the first five multiples of 5.
We can see that the multiples of 5 aren't stored in a sorted sequence in the array arr. To confirm this we'll display the elements of the array.
Displaying an array
The elements of an array can be simply displayed by doing console.log() of the array.
Now that we've created the array and displayed its elements let's sort the array such that the multiples of 5 are placed in increasing order.
Sorting an array
The arr array can be sorted using array sort. We need to call the sort() method with arr using dot (.) operator.
The sort array javascript method by default sorts the array in increasing order, thus there won't be any parameter passed.
The above line of code will perform the array sort and the array will be sorted in increasing order. We can check the new array by simply displaying its elements.
compareFunction
The compareFunction is an optional parameter in array sort method. If the compare function is not passed as the parameter of the sort() method, then it, by default sorts the elements by converting them into strings and comparing strings in UTF-16 code units order.
Note: The element type conversion (to string) is only done by the array sort function for comparison and the type of the array elements remains the same.
But, when the compareFunction is passed to the sort() method, the array elements are sorted according to the return value of the compareFunction in the sort array javascript method.
Syntax: The compareFunction takes two parameters a and b and returns three possible values: 0, negative or positive.
Following is the general form of the compareFunction:
Note: The compareFunction is a named function type in javascript.
Sort order based on compareFunction return value
Sometimes in an array, some elements are undefined. When such arrays are sorted using the default array sort method, the elements that are not undefined are sorted first, then the undefined elements are sorted to the end of the array.
When the compareFunction is passed to the array sort method, the array elements are sorted according to the return value of the function.
The following table describes the sort order of elements when the compareFunction is passed as a parameter:
| Return value of compareFunction(a, b) | Sort order |
|---|---|
| positive | sort b before a |
| negative | sort a before b |
| zero | keep the original order |
Example:
Let's sort an array of numbers in decreasing order using a compareFunction:
Output:
Note: You can refer the Sorting an array of numbers section for detailed explanation of sorting numeric arrays in decreasing order. The compareFunction is an anonymous function type.
Sorting an Array of Strings
As discussed earlier, the array of strings is sorted according to their sequences of UTF-16 code units values. By default the javascript array sort arranges the string elements in dictionary order, i.e. the elements that will appear first in the dictionary are placed first.
The time complexity of array sort is browser dependent. In modern versions of chrome, the time complexity of array sort will be O(n) whereas in firefox it is O(nlogn).
When the elements are either in uppercase or lowercase
Array sort in increasing order:
When the elements of an array are either in uppercase or lowercase, we can simply use the sort() method to sort the array in increasing order.
Example:
Explanation of the above example:
In the above example, the elements are strings. The sort function compares the elements in UTF-16 code units order and places them accordingly (or in simple words it arranges the elements as they would be in the dictionary). For example, in the original form of array, peach was placed before banana but according to dictionary arrangement peach would be placed after banana as peach starts with p and banana starts with b.
Array sort in decreasing order:
To sort the array in decreasing order when the elements of an array are either in uppercase or lowercase, we need to pass a compareFunction.
Example:
Note: The compareFunction is an arrow function type.
When there are mixed case elements
When the array elements are in mixed case, we need to pass a compareFunction. Inside the compareFunction, the elements are first converted into the same case (either lowercase or uppercase), then they are compared and placed accordingly.
Elements in the mixed case cannot be compared as they might give undesired results.
For e.g., while sorting an element in increasing order using the sort() method, logically Broadband should have been placed before computer as the former starts with the letter B and the latter starts with the letter c but in according to javascript array sort method computer will be placed before Broadband because c is placed before B according to UTF-16.
Example:
Note: a and b refer to the index and not the element. The compareFunction is an anonymous function type.
Sorting Non-ASCII Characters
The array sort method works fine for ASCII characters but for non-ASCII characters, it may produce unexpected results. Thus in order to sort the array elements that may have non-ASCII characters, we use the localeCompare() method.
The localeCompare() is a javascript method that returns a number indicating whether a reference string comes before, or after, or is the same as the given string in sort order.
ASCII is based on the English alphabet and consists of 128 characters, including A-Z, 0-9, punctuation, spaces, and other control codes that can be found on a standard English keyboard.
Example:
Let's sort an array of non-ASCII elements in increasing order.
In the above example, the array sort method is passed a compareFunction as a parameter. The function compares a and b using the localeCompare() method returns a number indicating whether a reference string comes before, or after, or is the same as the given string in sort order.
Note: The compareFunction is an anonymous function type.
Sorting an array of numbers
Why the sort( ) method isn't working for numbers?
The sort() method sometimes behaves unexpectedly when applied to an array of numbers. For e.g. let us sort an array of numbers in increasing order:
In the above example, we can see that the output is [ 10, 1000, 20, 35, 51 ] but the correct sequence should have been [ 10, 20, 35, 51, 1000 ].
This happens because the array sort methods convert the array elements into string before comparing them. Thus all the elements of the array arr are compared as strings (i.e 10 has become "10", 35 has become "35" and so on). Now when compared, the string "100" comes before the strings "20", "35" and "51" (as it has 1 as its first character which gives it precedence over mentioned string elements). This the sort() method places 1000 before 20, 35 and 51 in the resultant array.
How to Sort Array of Numbers?
To fix the above problem, a compareFunction is defined and passed to the array sort method as a parameter. The compareFunction definition should be defined such that it returns our desired result.
Note: refer the compareFunction section to learn how to define compareFunction
For the above problem, the compareFunction should be defined so that it sorts the array in increasing order. The sort() method passes the elements as parameters and then array sort happens according to the return value of the compareFunction. The compareFunction is an anonymous function type.
In the above example, the function is called with parameters a = 10 and b = 20, since the return value will be 10 - 20 (i.e. negative) so 10 will be placed before 20, similarly for a = 10 and b = 35, the return value will be 10 - 35 (i.e. negative) so 10 will be placed before 35 and so on. The function will compare all the elements and will place it according to the return value of compareFunction.
Sorting an Array of Objects by a Specified Property
In javascript, we can create an array of objects. Object in javascript is an entity that has a state and behavior. Objects in javascript may contain multiple key-value pairs.
Let us make an array of objects that store data about different cars:
Now, how do we sort this array?
From the above array, we can observe that the elements of the array have multiple keys (or properties) that may have the same or different data types.
Thus, compareFunction can be used to sort an array of objects. We should specify the property of the object which is used to compare the elements across the array.
Sorting objects by a numeric property
Let us sort the car array on the basis of increasing order of their price.
In the above example, the objects are passed as a parameter to the compare function.
In the compare function we are using the . operator to access the property which is used to compare the elements in array sort. The compareFunction is an anonymous function type.
Since the array is sorted on the basis of price, thus we are accessing the price of elements using a.price and b.price and returning the difference.
Sorting objects by the date property
Now suppose we want to array the elements in a way that the newest cars appear first and the oldest car appears last. In this case, we will have to sort the array by date property in decreasing order
The compareFunction here is an anonymous function type.
Sorting with Map
So far we have seen how the compareFunction is used to sort the array. As already discussed, the compareFunction is called using two parameters to return a result.
This may work smoothly for small arrays or simple functions, but when the array to be sorted is very large, or the function definition is complex, then it may result in a high overhead.
To avoid this situation, map is used. It is considered a more efficient method to perform the array sort.
In javascript, Map is a collection of elements where each element is stored as a Key, value pair.
In map sort, we basically traverse the array once to extract the actual values used for sorting and they are stored in a temporary array. Then we sort the temporary array and then traverse the temporary array to achieve the correct order.
Sort Stability
Sort stability means that the algorithm will maintain the relative order of records with equal keys.
Post EcmaScript 2019, the sort method in Javascript is stable.
Sort array javascript is stable method.
Example
Imagine we have an array stats of objects, where each object consists a name and a score.
As we can see, this array is pre-sorted by the name property. Now let us sort this array by score.
The above example will output an array sorted by score in increasing order. If we observe carefully, the score of Kane and Steve are the same, and upon sorting, the array sort method has maintained the same order as before calling the sort. This is the feature of a stable sort algorithm.
Browser Compatibility
| Method | Chrome | Edge | Firefox | Inernet Explorer | Opera | Safari |
|---|---|---|---|---|---|---|
| Sort | 1 | 12 | 1 | 5.5 | 4 | 1 |
| Stable sorting | 70 | 79 | 3 | n/a | 57 | 10.1 |
-
Columns indicate the browser names and the compatibility of each tag with each browser.
-
If the row contains a number (for example, 1 for Firefox), it indicates that the browser version specified is the bare minimum required to support the tag.
-
n/a means that the browser doesn't support that functionality.
Conclusion
- The array sort method in javascript is used to sort the arrays in javascript.
- By default, arrays are sorted in increasing order.
- The array sort method converts the array elements into strings before sorting.
- A function (compareFunction) can be passed to the array sort method as a parameter. This isn't a mandatory parameter.
- The compareFunction takes array elements as parameter and returns either a positive value, negative value or 0.
- The sort() method doesn't work properly for numbers, or non-ASCII characters.
- Array sort can be performed with respect to different properties of elements.
- Arrays in javascript can be sorted using a map.
- The array sort method in javascript is stable.