Comparison sorting algorithms normally evaluate 2x elements at each step (and do something different if the first element is smaller/bigger than or equal to the second element.)

What are some examples of sorting algorithms, preferably stable ones, where more than 2x elements can be compared at each step?

How would their performance be evaluated?

For sorting 2 elements at a time, a comparison sort cannot perform better than O(n log n) on average, what's the performance limit for sorting 3, 4, 5 elements at a time?

CodePudding user response：

Any n-element at a time (for a specified fixed n) comparisons can be emulated by a series of some fixed number of 2-element at a time comparisons. If you could do better than O(n log n) on n-at-a-time, it would automatically give you a better than O(n log n) algorithm for 2-at-a-time.

CodePudding user response：

A k-way merge sort needs to determine which of k elements is the smallest. Using a standard 2x compare, it will take 3 compares to determine the smallest element. For a memory based sort, a 4-way merge sort will take the about the same number of operations as a 2-way merge sort, but gets a slight improvement in running time due to being more cache friendly. There is an example of a 4 way merge sort at the end of this answer:

Optimized merge sort faster than quicksort

On a system with 16 registers, 4-way is about as high as you can go. Plus trying to implement this without using a heap (which results in a slower algorithm) requires a large nested tree of if | else statements. It's already complex enough in the 4-way merge sort in that answer linked to above.