### forum-msg-id-131304-edit

Original date:2017-08-11 16:59:18 Edited by: petelomax Subject: Re: Natural sort comparison

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
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).

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