Know Your Sorting Algorithm | Set 1 (Sorting Weapons used by Programming Languages) - GeeksforGeeks
Ever wondered how sort() function we use in C++/Java or sorted() in Python work internally?
Here is a list of all the inbuilt sorting algorithms of different programming languages and the algorithm they use internally.
- C's qsort() – Quicksort
- Best Case Time Complexity- O(NlogN)
- Average Case Time Complexity- O(NlogN)
- Worse Case Time Complexity- O(N2)
- Auxiliary Space- O(log N)
- Stable- Depends on the implementation of the comparator function
- Adaptive- No
- C++'s sort() – Introsort (Hybrid of Quicksort, Heap Sort and Insertion Sort)
- Best Case Time Complexity- O(NlogN)
- Average Case Time Complexity- O(NlogN)
- Worse Case Time Complexity- O(NlogN)
- Auxiliary Space- O(logN)
- Stable- No
- Adaptive- No
- C++'s stable_sort() – Mergesort
- Best Case Time Complexity- O(NlogN)
- Average Case Time Complexity- O(NlogN)
- Worse Case Time Complexity- O(NlogN)
- Auxiliary Space- O(N)
- Stable- Yes
- Adaptive- Yes
- Java 6's Arrays.sort() – Quicksort
- Best Case Time Complexity- O(NlogN)
- Average Case Time Complexity- O(NlogN)
- Worse Case Time Complexity- O(N2)
- Auxiliary Space- O(logN)
- Stable- Depends
- Adaptive- No
- Java 7's Arrays.sort() – Timsort (Hybrid of Mergesort and Insertion Sort)
- Best Case Time Complexity- O(N)
- Average Case Time Complexity- O(NlogN)
- Worse Case Time Complexity- O(NlogN)
- Auxiliary Space- O(N)
- Stable- Yes
- Adaptive- Yes
- Java's Collections.sort() – Mergesort
- Best Case Time Complexity- O(NlogN)
- Average Case Time Complexity- O(NlogN)
- Worse Case Time Complexity- O(NlogN)
- Auxiliary Space- O(N)
- Stable- Yes
- Adaptive- Yes
- Python's sorted() – Timsort (Hybrid of Mergesort and Insertion Sort)
- Best Case Time Complexity- O(N)
- Average Case Time Complexity- O(NlogN)
- Worse Case Time Complexity- O(NlogN)
- Auxiliary Space- O(N)
- Stable- Yes
- Adaptive- Yes
- Python's sort() – Timsort (Hybrid of Mergesort and Insertion Sort)
- Best Case Time Complexity- O(N)
- Average Case Time Complexity- O(NlogN)
- Worse Case Time Complexity- O(NlogN)
- Auxiliary Space- O(N)
- Stable- Yes
- Adaptive- Yes
Read full article from Know Your Sorting Algorithm | Set 1 (Sorting Weapons used by Programming Languages) - GeeksforGeeks
No comments:
Post a Comment