I have a large sequence of simple structs, about 5M long. I print its repr before and after sorting. It has lots of data before, but it's all zeroes after -- except the first element, which is unchanged.
What could explain this behavior? I suspect the merge-sort itself.
import algorithm
type
seq_coor_t* = cint
d_path_data2* = object
d*: seq_coor_t
k*: seq_coor_t
pre_k*: seq_coor_t
x1*: seq_coor_t
y1*: seq_coor_t
x2*: seq_coor_t
y2*: seq_coor_t
proc compare_d_path*(arg1, arg2: d_path_data2): int =
if arg1.d - arg2.d == 0:
return arg1.k - arg2.k
else:
return arg1.d - arg2.d
proc d_path_sort*(path_base: var seq[d_path_data2]) =
echo "sort:", len(path_base), " max:", $max_idx)
path_base.sort(compare_d_path)
#qsort(base, max_idx, sizeof(d_path_data2), compare_d_path);
This was originally in C, and I will probably need to use qsort anyway, so I can avoid sorting the unused portion of the array. (I wish Nim offered an ArrayView, compatible with openarray.) But it's disturbing that I cannot can expected behavior from this standard algorithm. Any ideas?
(Yes, I've run newSeq before assigning value. Yes, I use debug mode.)
Oh! I think I know: My comparator returns a difference, which is fine for qsort. But I'll bet algorithm.sort expects strictly [-1, 0, 1].
I'll try with that and post later...
... Nope, no joy. In fact, both the old and new comparator work fine with binarySearch. (I'll submit my modified version to Nim in GitHub soon.)
So this is a real mystery.
I am now using qsort successfully, with some extra work to get a pure "C" comparator. But the mystery remains....