Answers to: Fastest sorting algorithm .https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm<p>Which is the fastest sorting algorithm?</p>enFri, 24 Feb 2017 12:48:34 +0530Answer by inovation123https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/91815<p>C++ STL sort function is fastest. If you want your own implementation then randomized quick sort and heap sort are really good candidates as they are universal unlike radix sort which is O(n) but demands keys in lexicographic order.</p>
<p>Thus, overall inbuilt sort functions are quite fast and are thus widely used</p>inovation123Fri, 24 Feb 2017 12:48:34 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/91815Answer by sanahhttps://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88367<p>fastest sorting algorithm will be the merge sort.since the time complexity is less even in the worst case(nlogn).Even if the array is properly arranged or not,it wouldn't take more than nlogn steps to sort the array.</p>sanahSat, 26 Nov 2016 20:15:54 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88367Answer by lawliet_yagamihttps://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88352<p>Well there's no de facto 'fastest sorting algorithm (Else there'd be just one sorting algorithm and everybody would've used that). It all depends on how the input data is.</p>
<ul>
<li>If the array is nearly sorted, then <strong>Insertion sort, Selection sort</strong> would be the algorithm of my choice.</li>
<li>If I already know the input elements range, eg. If I want to sort 1 billion characters, I know there're just 26 unique elements, I'd go with <strong>Counting sort</strong></li>
<li>If I'm sorting objects, I want the sort to be stable. I'd use Java's Collections.sort() which internally uses <strong>Tim Sort</strong></li>
<li>If I'm just sorting random numbers of which I have no data about(eg. range), I'd use Java's Arrays.sort() which uses <strong>Double Pivoted Quick sort</strong></li>
</ul>lawliet_yagamiSat, 26 Nov 2016 19:32:19 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88352Answer by app_geekhttps://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88346<p>in java Arrays.sort(arr_name);</p>app_geekSat, 26 Nov 2016 18:07:08 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88346Answer by bkishan29https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88344<p>I use sorted().This is built-in in Python and is over 4 times faster than other sorting techniques.</p>bkishan29Sat, 26 Nov 2016 11:15:19 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88344Answer by wefgefhttps://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88316<p>For competitive programming purposes, the standard library sort() should do just fine. In C++ it is an implementation of <a href="https://en.wikipedia.org/wiki/Introsort">introsort</a>.
Mergesort is often not a great candidate because of all the extra memory used.</p>
<p>On a side note, there is a sorting algorithm, <a href="https://en.wikipedia.org/wiki/Block_sort">block sort</a>, that:</p>
<ul>
<li>Uses O(1) extra memory</li>
<li>Is stable</li>
<li>Runs in O(N log N) in worst case</li>
<li>Runs in O(N) in best case</li>
</ul>wefgefFri, 25 Nov 2016 18:05:07 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88316Answer by akashbhalotiahttps://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88292<p>1)<strong>Merge Sort</strong> is unarguably the fastest sorting algorithm with a worst-case complexity= <strong>O(n logn)</strong> . This means that whatever be the arrangement of the elements in the array, it won't take more than n*logn steps to sort the array. A standard computer generally takes 1 second to perform 10^8 such steps/operations. An important point to note here is that the base of the logarithm is 2 and not 10 or e as generally taken in schools. The <strong>only disadvantage</strong> of Merge Sort is that it requires <strong>extra space</strong> , i.e. an extra array to merge the sorted elements into. This is important to know because sometimes additional space has a great cost attached with it.</p>
<p>2)<strong>Quicksort</strong> is usually the sorting algorithm that is used everywhere. A few examples of this would be the inbuilt java, C++ sorting functions, MS Excel ,etc. Quicksort has an average worst-case complexity of <strong>O(n logn)</strong> but a worst-case complexity of <strong>O(n^2)</strong>. However, this only occurs when the array is already sorted and can be overcome by randomizing the position of the pivot everytime. This is a very convenient technique since it does not have the additional cost of an entire new array.</p>akashbhalotiaFri, 25 Nov 2016 00:27:36 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88292Answer by mathecodicianhttps://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88291<p>This is a good link for time complexity of various algorithms and data structures.</p>
<p><a href="http://bigocheatsheet.com/">http://bigocheatsheet.com/</a></p>mathecodicianThu, 24 Nov 2016 23:58:43 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/88291Answer by pkienhttps://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/87313<p>I think quick sort is faster than merge sort(don't require much memory,and simpler operation in the inner loop). But i must say <code>std::sort</code> is the best sort and doesn't require effort to code the algorithm.</p>pkienThu, 10 Nov 2016 17:22:10 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/87313Answer by kay_kayhttps://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/87280<p><a href="https://www.quora.com/What-is-the-fastest-sorting-algorithm">Refer this link</a></p>kay_kayThu, 10 Nov 2016 00:48:35 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/87280Answer by srd091https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/87279<p><strong>Merge Sort</strong> is the fastest stable sorting algorithm with worst-case complexity of <strong>O(nlogn)</strong>, but it requires extra space. Although, if memory constraints are very tight you can use <strong>Quick Sort</strong>, whose worst-time compelxity is O($n^{2}$) but average case complexity is <strong>O(nlogn)</strong>.
<br>
A sorting algorithm is stable if whenever there are two records <strong>R</strong> and <strong>S</strong> with the same key, and <strong>R</strong> appears before <strong>S</strong> in the original list, then <strong>R</strong> will always appear before <strong>S</strong> in the sorted list.</p>
<p><br><br>
If you feel your question has been answered, mark it as accepted.</p>srd091Thu, 10 Nov 2016 00:44:23 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/87279Answer by bansal1232https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/87278<p>Inbuilt function of sort available in "algorithm" header file of C/C++.. sort() are much faster than any other implemented sort!!</p>bansal1232Thu, 10 Nov 2016 00:44:04 +0530https://discuss.codechef.com/questions/87274/fastest-sorting-algorithm/87278