OpenEuphoria

Re: Natural sort comparison

• Posted by petelomax Aug 11, 2017
• 1977 views

I found a way to improve quick_sort for the all-1s case, along with a minor speedup for the swap:

function quick_sort(sequence s) 
sequence qstack 
integer first, last, stackptr, I, J 
--object tmp, pivot 
object pivot, ti, tj 
 
    qstack = repeat(0,floor((length(s)/5)+10))    -- create a stack 
 
    first = 1 
    last = length(s) 
    stackptr = 0 
    while 1 do 
        while first<last do 
--maybe?: 
--          if last-first<=100 then 
--              s[first..last] = insertion_sort(s[first..last]) 
--              exit 
--          end if 
            pivot = s[floor((last+first)/2)] 
            I = first 
            J = last 
            while 1 do 
--              while s[I]<pivot do 
                while 1 do 
                    ti = s[I] 
                    if ti>=pivot then exit end if 
                    I += 1 
                end while 
--              while s[J]>pivot do 
                while 1 do 
                    tj = s[J] 
                    if tj<=pivot then exit end if 
                    J -= 1 
                end while 
                if I>J then exit end if 
                if I<J then 
                    -- added 6/8/17: 
                    if ti=tj then 
                        {I,J} = {J+1,I-1} 
                        exit 
                    end if 
--                  tmp = s[I] 
--                  s[I] = s[J] 
--                  s[J] = tmp 
                    s[I] = tj 
                    s[J] = ti 
                end if 
                I += 1 
                J -= 1 
                if I>J then exit end if 
            end while 
            if I<last then 
                qstack[stackptr+1] = I 
                qstack[stackptr+2] = last 
                stackptr += 2 
            end if 
            last = J 
        end while 
        if stackptr=0 then exit end if 
        stackptr -= 2 
        first = qstack[stackptr+1] 
        last = qstack[stackptr+2] 
    end while 
    return s 
end function 

Which makes it the clear winner across the board in my "Compare_sorting_algorithms.exw".

Given the performance boost that qstack gives to quick_sort, I wonder whether a similar technique could be applied to merge_sort, likewise turning it from a recursive algorithm to an iterative one, and whether merges could be performed in-situ. I jotted down some outline thoughts:

A stack of length log2 might be enough? Or even ceil(log2(n))-6 if we farm out length<=64 to insertion_sort.

Consider the merge operation of merge_sort, being performed in-situ.
(Note that <done> may in fact be a segment awaiting a future merge with merge(A,B))

xxxxxx,a1,a2,a3,a4,a5,b1,b2,b3,b4,b5 
<done> <----- A ----> <----- B ----> 

Now, if we pick a1, then all that happens is that A shrinks. A' and B remain sorted.
If we pick b1, then a1 must move into that slot. At this stage the rest of B remains sorted, whereas A becomes (not for long) a still-sorted-but-now-circular list.

At some point, however, the circular list aspect of A breaks down (assuming we would rather not physically re-order it), eg:

xxxxx,b1,b2,b3,a4,a5,a1,a2,a3,b4,b5 
<--- done ---> <----- A ----> <-B-> 

(pick a1)

xxxxx,b1,b2,b3,a1,a5,a4,a2,a3,b4,b5 
<----- done ----> <--- A ---> <-B-> 

The obvious solution is to maintain A as a linked list, which can be done using a parallel sequence links, initially the same size as the sequence x being sorted.
There may be opportunities to preset that links sequence during some prior merge operation (but probably not if we palm off short sequences to insertion_sort) - then again maintaining it for the B is pointless.

Lastly, if the merge terminates because A became empty, then any remainder of B is already in place, whereas if B becomes empty, then A must be reordered, using the same linked list, obviously with null-ops for any head(A)==A[1].

Pete