Explain Array's sort method for sorting numbers. What is the time complexity of this method ?

Q: Explain Array's sort method for sorting numbers. What is the time complexity of this method ?

Sorting an array with sort method is easy if the array elements are letters : var fruits = ["Banana", "Orange", "Apple", "Mango"]; fruits.sort(); console.log(fruits) // output [ 'Apple', 'Banana', 'Mango', 'Orange' ] But if the array elements are Numbers , it becomes a bit tricky . Because , if numbers are sorted as strings, "25" is bigger than "100", because "2" is bigger than "1". You can fix this by providing a "compare function" as a parameter to the sort method : for example : let arr = [20, 10 , 5 , 40 , 100] arr.sort(function(a, b){return a-b}) console.log(arr) //output : [5, 10, 20, 40 , 100] Now , regarding Time complexity , Basically it varies from browser to browser. Following is the explanation : Firefox uses merge sort. Chrome, as of version 70, uses a hybrid of merge sort and insertion sort called Timsort. The time complexity of merge sort is O(n log n) . While the specification does not specify the sorting algorithm to use, in any serious environment, you can probably expect that sorting larger arrays does not take longer than O(n log n) (because if it did, it would be easy to change to a much faster algorithm like merge sort, or some other log-linear method). While comparison sorts like merge sort have a lower bound of O(n log n) (i.e. they take at least this long to complete), Timsort takes advantages of "runs" of already ordered data and so has a lower bound of O(n).

Question

Accepted Answer

Sorting an array with sort method is easy if the array elements are letters :


var fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits.sort();
console.log(fruits)  // output [ 'Apple', 'Banana', 'Mango', 'Orange' ]

But if the array elements are Numbers , it becomes a bit tricky . Because , if numbers are sorted as strings, "25" is bigger than "100", because "2" is bigger than "1". You can fix this by providing a "compare function" as a parameter to the sort method : for example :


let  arr = [20, 10 , 5 , 40 , 100]
arr.sort(function(a, b){return a-b}) 
console.log(arr)  //output : [5, 10, 20, 40 , 100]

Now , regarding Time complexity , Basically it varies from browser to browser. Following is the explanation : Firefox uses merge sort. Chrome, as of version 70, uses a hybrid of merge sort and insertion sort called Timsort. The time complexity of merge sort is O(n log n). While the specification does not specify the sorting algorithm to use, in any serious environment, you can probably expect that sorting larger arrays does not take longer than O(n log n) (because if it did, it would be easy to change to a much faster algorithm like merge sort, or some other log-linear method). While comparison sorts like merge sort have a lower bound of O(n log n) (i.e. they take at least this long to complete), Timsort takes advantages of "runs" of already ordered data and so has a lower bound of O(n).