search

ameekkhan / ameeqsort

A new recursive MergeSort++ which is a variant of classical merge sort.
MIT License
1 stars 1 forks source link

Stability #1

Open scandum opened 2 years ago

scandum commented 2 years ago

I took a quick look at your code, which looks great btw, and noticed the sort might not be stable.

// array[0] and array[2]
// array[1] and array[3]
// array[0] and array[1]
// array[2] and array[3]
// array[1] and array[2]

If you change this to:

// array[0] and array[1]
// array[2] and array[3]
// array[1] and array[2]
// array[0] and array[1]
// array[2] and array[3]
// array[1] and array[2]

it should be stable, since you'll always be comparing adjacent elements. It's possible to do it with 5 comparisons, but you'll need a pretty complex decision tree to keep it stable.

ameekkhan commented 2 years ago

I am very glad that you like my sort. I am very thankful for your correction to this algorithm now it will be stable. And I will test it and also compare it with all other sorts its execution times.