Bucketsort

QB64

<lang B64> REDIM a(0 to 1048575) FOR FillArray& LBOUND(a) to UBOUND(a)

   a(Fillearray&) = RND

NEXT DoRecurse% = -1 DemoOrder& = 1 ' -1 = descending, 1 = desecending BucketSort a(), LBOUND(a), UBOUND(a), DemoOrder&, DoRecurse% '* without the recursive initial call, executiom time is FAR slower.

SUB BucketSort (Array() AS DOUBLE, start AS LONG, finish AS LONG, order&, recurse%)

   DIM BS_Local_NBuckets AS INTEGER
   DIM BS_Local_ArrayRange AS DOUBLE
   DIM BS_Local_N AS LONG
   DIM BS_Local_S AS LONG
   DIM BS_Local_Z AS LONG
   DIM BS_Local_Remainder AS INTEGER
   DIM BS_Local_Index AS INTEGER
   DIM BS_Local_Last_Insert_Index AS LONG
   DIM BS_Local_Current_Insert_Index AS LONG
   DIM BS_Local_BucketIndex AS INTEGER
   REDIM BSMMrec AS MinMaxRec
   GetMinMaxArray Array(), start, finish, BSMMrec
   BS_Local_ArrayRange = Array(BSMMrec.max) - Array(BSMMrec.min)
   IF BS_Local_ArrayRange > 0 THEN
       BS_Local_NBuckets = 2 * INT(LOG(finish - start + 1) / LOG(2)) + 1
       BS_Local_N = (finish - start)
       BS_Local_Remainder = BS_Local_N MOD BS_Local_NBuckets
       BS_Local_NBuckets = BS_Local_NBuckets - 1
       REDIM BS_Buckets_Array(BS_Local_NBuckets, 0 TO (BS_Local_NBuckets * (1 + (BS_Local_N - BS_Local_Remainder) / BS_Local_NBuckets))) AS DOUBLE
       REDIM BS_Count_Array(0 TO BS_Local_NBuckets) AS LONG
       FOR BS_Local_S = start TO finish
           BS_Local_BucketIndex = BS_Local_NBuckets * ((Array(BS_Local_S) - Array(BSMMrec.min)) / BS_Local_ArrayRange)
           BS_Buckets_Array(BS_Local_BucketIndex, BS_Count_Array(BS_Local_BucketIndex)) = Array(BS_Local_S)
           BS_Count_Array(BS_Local_BucketIndex) = BS_Count_Array(BS_Local_BucketIndex) + 1
       NEXT
       BS_Local_Last_Insert_Index = start
       BS_Local_Current_Insert_Index = start
       FOR BS_Local_S = 0 TO BS_Local_NBuckets
           IF BS_Count_Array(BS_Local_S) > 0 THEN
               BS_Local_Last_Insert_Index = BS_Local_Current_Insert_Index
               FOR BS_Local_Z = 0 TO BS_Count_Array(BS_Local_S) - 1
                   Array(BS_Local_Current_Insert_Index) = BS_Buckets_Array(BS_Local_S, BS_Local_Z)
                   BS_Local_Current_Insert_Index = BS_Local_Current_Insert_Index + 1
               NEXT
               IF recurse% THEN
                   '* Withoit this, 28s+
                   BucketSort Array(), BS_Local_Last_Insert_Index, BS_Local_Current_Insert_Index - 1, order&, 0
               ELSE
                   InsertionSort Array(), BS_Local_Last_Insert_Index, BS_Local_Current_Insert_Index - 1, order&
               END IF
           END IF
       NEXT
       ERASE BS_Buckets_Array, BS_Count_Array
   END IF

END SUB </lang>