[prev in list] [next in list] [prev in thread] [next in thread] 

List:       busybox
Subject:    stable sort? (sort -s)
From:       Assaf Gordon <assafgordon () gmail ! com>
Date:       2017-08-22 23:35:47
Message-ID: a5ca76d5-6987-9b85-6846-969135982e0b () gmail ! com
[Download RAW message or body]

Hello,

Does busybox's sort implements a stable sort?

I see it accepts "-s" option,
and I see in the source code that FLAG_s
does disable the last-resort comparison:
 https://git.busybox.net/busybox/tree/coreutils/sort.c#n343

However,
It seems the code also uses qsort() which is not stable -
rendering the stable-ness ineffective (IUUC).

I've encountered a case on alpine linux 3.6.2/amd64,
with busybox v1.26.2 (2017-08-03 13:08:12 GMT)
where using "-s" returns mis-ordered results:

  $ printf "a X 1\nA X 2\nA x 5\n" | sort -k1,1
  A X 2
  A x 5
  a X 1

  $ printf "a X 1\nA X 2\nA x 5\n" | sort -k1,1 -s
  A x 5
  A X 2
  a X 1

Whereas with these give the same result (as they should) with
coreutil's, FreeBSD and OpenBSD's sort.

An alpine developer responded on alpine-user@ mailing list:
 "It uses qsort() that is not stable by default.  It could have been
 made stable by adding line number to the comparison key, however there
 is no evidence of any attempt for it."

If this is the case,
perhaps it's worth disabling "-s" - otherwise it can mislead to give
incorrect results?


Thoughts?
regards,
 - assaf

_______________________________________________
busybox mailing list
busybox@busybox.net
http://lists.busybox.net/mailman/listinfo/busybox
[prev in list] [next in list] [prev in thread] [next in thread]