1. Merge sort not stable

  • Posted by Spock Jan 21, 2011
  • 1578 views

Hi,

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

Spock

new topic     » topic index » view message » categorize

Search



Quick Links

User menu

Not signed in.

Misc Menu