Sub TestTimSort
Dim NUM_TESTS As Int = 1000 '<--- Do some random tests with several sizes and run lengths to verify that it works
For k=0 To NUM_TESTS-1
Dim i As Int
Dim iSize As Int = Rnd(50,400)
Dim arrInt(iSize) As Int
For i = 0 To iSize - 1
arrInt(i) = Rnd(0, 400)
Next
iConstRun = Rnd(iSize/4, iSize/2)
TimSort(arrInt, arrInt.Length)
'For i = 0 To iSize - 1
' Log(i & " - " & arrInt(i))
'Next
For i=1 To iSize-2
If arrInt(i)>arrInt(i+1) Then
Log($"-----> Test ${k} failed!"$)
Exit
End If
Next
If i=iSize-1 Then Log($"Test ${k} correct"$)
Next
End Sub
Sub TimSort(arrInt() As Int, n As Int)
Dim i As Int
Dim lSize As Int
Dim lBegin As Int
Dim lEnd As Int
Dim lMid As Int
For i = 0 To n - 1 Step iConstRun
TimInsertion(arrInt, i, Min(i + iConstRun-1, n - 1)) '<---- HERE, replace '31' by 'iConstRun-1'
'i = i + iConstRun
Next
lSize = iConstRun
Do While lSize<=n-1
'For lSize = iConstRun To n - 1 '<-- In this case we don't use 'For' since the step is not constant
For lBegin = 0 To n - 1 Step 2*lSize '<-- should be done like this
lEnd = Min(lBegin + 2 * lSize - 1, n - 1)
lMid = lBegin + lSize - 1
If lMid<lEnd Then '<-- Add this condition to prevent crashes when size is not a multiple of run.
TimMerge(arrInt, lBegin, lMid, lEnd)
End If
'lBegin = lBegin + (2 * lSize) '<-- incorrect
Next
Log("done")
lSize = lSize * 2
'Next
Loop
End Sub
Sub TimInsertion(arrInt() As Int, lBegin As Int, lEnd As Int)
Dim i As Int
Dim j As Int
Dim lTemp As Int
For i = lBegin + 1 To lEnd
lTemp = arrInt(i)
j = i - 1
Do While CheckWhile(j, lBegin, arrInt, lTemp)
arrInt(j + 1) = arrInt(j)
j = j - 1
Loop
arrInt(j + 1) = lTemp
Next
End Sub
Sub CheckWhile(j As Int, lBegin As Int, arrInt() As Int, lTemp As Int) As Boolean
If j < 0 Then
Return False
End If
If j >= lBegin Then
If arrInt(j) > lTemp Then
Return True
End If
End If
Return False
End Sub
Sub TimMerge(arrInt() As Int, lLeft As Int, lMid As Int, lRight As Int)
Dim i As Int
Dim j As Int
Dim k As Int
Dim Len1 As Int
Dim Len2 As Int
Len1 = lMid - lLeft + 1
Len2 = lRight - lMid
Dim arrBegin(Len1) As Int
Dim arrEnd(Len2) As Int
For i = 0 To Len1 - 1
arrBegin(i) = arrInt(lLeft + i)
Next
For i = 0 To Len2 - 1
arrEnd(i) = arrInt(lMid + 1 + i)
Next
i = 0
j = 0
k = lLeft
Do While i < Len1 And j < Len2
If arrBegin(i) <= arrEnd(j) Then
arrInt(k) = arrBegin(i)
i = i + 1
Else
arrInt(k) = arrEnd(j) '<<<<< goes wrong here, too low values go to the array!
j = j + 1
End If
k = k + 1
Loop
Do While i < Len1
arrInt(k) = arrBegin(i)
k = k + 1
i = i + 1
Loop
Do While j < Len2
arrInt(k) = arrEnd(j)
k = k + 1
j = j + 1
Loop
End Sub