5 ms·
Merge sort: s = (lo, hi) -> if lo==hi return if lo+1==hi if VA.gt(lo,hi) VA.swap(lo,hi) return mid=
by jxcole 15y ago
Merge sort:
s = (lo, hi) ->
if lo==hi
return
if lo+1==hi
if VA.gt(lo,hi)
VA.swap(lo,hi)
return
mid=Math.floor(lo+(hi-lo)/2)
s(lo,mid)
s(mid+1,hi)
mid++
while lo<=mid && mid<=hi
if VA.gt(lo,mid)
VA.insert(mid, lo)
mid++
else
lo++
s(0,VA.length)
- derobert 15y agoMerge sort w/o using insert (and probably with some bugs...): tmp = VA.length merge = (start1, start2, end2) -> out = start1 end1 = start2 - 1 for x in [tmp+out .. tmp+end2] if start1 <= end1 && start2 <= end2 if VA.lt(start1, start2) VA.swap(start1, x) ++start1 else VA.swap(start2, x) ++start2 else if start1 <= end1 VA.swap(start1, x) ++start1 else VA.swap(start2, x) ++start2 for x in [out..end2] VA.swap(x, tmp+x) mergesort = (left, right) -> if (right - left) == 1 if VA.gt(left, right) VA.swap(left, right) else if (right - left) == 0 /* do nothing */ else split = Math.floor((right-left)/2) + left; mergesort(left, split - 1) mergesort(split, right) merge(left, split, right) mergesort(0, VA.length - 1)
- thedufer 15y agoAdded as a prewritten sort. Thanks!
- deleted 15y ago[deleted]