dependance of sorting time on number of different items

[tsh73]

While testing for this thread
justbasiccom.proboards.com/thread/1052/occurrences-counting
I noticed that time that SORT takes depends on how many different values are in.

Here's the test code, compared with qsort from JB example folder.
You see?
QSort takes about same time
while built-in SORT obvoiusly has troubles sorting similar numbers
(and if array is the same it takes even longer time then QSort written in BASIC!)

so I wonder
1) what algorhithm JB/LB uses for SORT
2) is it right/expected/normal behaviour for this algorhithm
3) or there is some error in code making it work longer?

Size of array N = 10000
--------------------
Num different, ~ 10000
built-in sort 94
example qsort 4515
--------------------
Num different, ~ 100
built-in sort 141
example qsort 4562
--------------------
Num different, ~ 10
built-in sort 672
example qsort 4235
--------------------
Num different, ~ 2
built-in sort 3187
example qsort 4484
--------------------
Num different, ~ 1
built-in sort 6859
example qsort 4484
-- Over --


N=10000
dim a$(N)

kList$ = N;" 100 10 2 1"

print "Size of array N = ";N
for j = 1 to 5
   k=val(word$(kList$, j))
   print "--------------------"
   print "Num different, ~ ";k

   'sort  ======================================
   gosub [generate]
   t8=time$("ms")
   sort a$(),a1,N
   t9=time$("ms")
   print "built-in sort ";t9-t8

   'qsort  ======================================
   gosub [generate]
   t8=time$("ms")
   call QSort 1, N
   t9=time$("ms")
   print "example qsort ";t9-t8

next
print " -- Over --"

end

sub QSort Start, Finish
 i = Start
 j = Finish
 x$ = a$(int((i+j)/2))
 while i <= j
   while a$(i) < x$
     i = i + 1
   wend
   while a$(j) > x$
     j = j - 1
   wend
   if i <= j then
     a$ = a$(i)
     a$(i) = a$(j)
     a$(j) = a$
     i = i + 1
     j = j - 1
   end if
 wend
 if j > Start then call QSort Start, j
 if i < Finish then call QSort i, Finish
end sub

'-------------------------------
[generate]

randomize .001  'same numbers for both sorts
't0=time$("ms")

for i = 1 to N
   a$(i) = "item";int(rnd(1)*k)
next
't1=time$("ms")

'print "generating ";t1-t0
return


[tsh73]

Here's results for LB5.353
QSort works 3x faster then in JB/LB4 :)
Built-in sort behaves much more reasonable.
So I believe there must be some error in LB/JB codebase...
Size of array N = 10000
--------------------
Num different, ~ 10000
built-in sort 578
example qsort 1549
--------------------
Num different, ~ 100
built-in sort 306
example qsort 1244
--------------------
Num different, ~ 10
built-in sort 244
example qsort 1298
--------------------
Num different, ~ 2
built-in sort 223
example qsort 1443
--------------------
Num different, ~ 1
built-in sort 209
example qsort 1266
-- Over --

[honky]

In response to this thread: justbasiccom.proboards.com/thread/1052/occurrences-counting?page=1&scrollTo=7525
You are sorting a strings array.
Question on how many characters is sorting ?

[plus]

As I recall JB has peculiar string compare. Some string compare methods handle lower and upper case differently, ie listing all caps A-Z before starting lower case "a" words, so Zebra comes before apple.

So how strings are being compared might account for differences in sort time, not to mention results!!! For instance case insensitive sorts need only concern themseleves with 26 letters whereas case sensitive sorts have 52 symbols to deal with.

b = b + ...

[tsh73]

10000 lines of "item0".."item9999", 5 to 8 characters

But I tried sort with 10000 random strings from 5 to 1000 characters
And the lime taken by sort happened to be the same.

[tsh73]

Just converted program to sort numeric arrays
Same problem