Is Quick Sort the Most Efficient Sorting Algorithm Available?

AI Thread Summary
The discussion centers on the efficiency of sorting algorithms, particularly quicksort, and the potential for discovering a perfect sorting algorithm. While quicksort is popular due to its ease of implementation and generally good performance, it has a worst-case time complexity of O(n^2), making it less efficient than other algorithms like merge sort and heap sort, which both have a worst-case complexity of O(n log n). However, in practice, merge sort and heap sort can be slower than quicksort. Merge sort may outperform quicksort when dealing with larger data sizes, especially when using pointers. Additionally, a hybrid approach combining radix (bucket) sort with merge sort has been noted as the fastest for true random data, albeit at the cost of higher memory usage. Previous discussions and test results related to sorting algorithms are referenced for further insights.
viv0411
Messages
1
Reaction score
0
Is quick sort the most efficient algorithm or there is a possibility of a perfect sorting algorithm to be discovered?
 
Technology news on Phys.org
quick sort isn't even the most efficient current algorithm, it's worst case is O(n^2) but is quick and easy to code and the inner loop fits in the CPU cache so is fast enough normally.

merge and heap sorts are both O(n ln n) worst case but in practice are slower.
 
Merge sort can be faster than quicksort, especially when using pointers to data where the average compare size (before a mismatch) is greater than a pointer size. For true random data, I used a hybrid radix (bucket) / merge sort, which was the fastest, but required a large amount of memory.

Previous threads on sorting. I included some test results in post #16 of the thread in the first link:

https://www.physicsforums.com/showthread.php?t=218369

https://www.physicsforums.com/showthread.php?t=181589
 

Thread 'Learning Assembly and computer architecture for x86'

Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
View full post »

Thread 'Microsoft Technical Interview question'

I had a Microsoft Technical interview this past Friday, the question I was asked was this : How do you find the middle value for a dataset that is too big to fit in RAM? I was not able to figure this out during the interview, but I have been look in this all weekend and I read something online that said it can be done at O(N) using something called the counting sort histogram algorithm ( I did not learn that in my advanced data structures and algorithms class). I have watched some youtube...
View full post »

Similar threads

DeepMind AI Develops Efficient Sorting Algorithms
Replies
7
Views
2K
Sorting an Array of 2-D Records
Replies
6
Views
1K
Learning data structures and algorithms in different programming languages
2
Replies
84
Views
557
How are there so many sorting algorithms?
Replies
10
Views
4K
Physical representation of bead sort
Replies
2
Views
1K
Is this considered a valid sorting algorithm?
Replies
8
Views
2K
MHB Selection Sort & Insertion Sort: Step-by-Step Guide to Sorting Data
Replies
3
Views
2K
Can Sorting Ever Be Done in Time Proportional to n?
Replies
12
Views
2K
How Can We Efficiently Parallelize the N-Queens Problem?
Replies
11
Views
4K
How do you handle algorithms (memorize vs. reference)?
Replies
13
Views
3K

Hot Threads

Recent Insights

Back
Top