1. Merge sort not stable


While working on a multi-column database viewer I was comparing the performance of different sort algorithms and discovered that the Merge sort in allsorts.ex is not stable. I don't have the very latest version of Euphoria yet so I wouldn't know if this had been fixed or not. The problem is this line:

if compare(a[1], b[1]) < 0 then 

It should be:

if compare(a[1], b[1]) <= 0 then 

Merge sort is quite good on large data sets. It's not the fastest but it is stable, unlike Shell sort which is part of Euphoria's std library. Some other languages use Merge sort as their default. FYI


new topic     » topic index » view message » categorize


Quick Links

User menu

Not signed in.

Misc Menu