[bmx] Merge Sort TList by N [ 1+ years ago ]

[BlitzBot]

Title : Merge Sort TList
Author : N
Posted : 1+ years ago

Description : Short description says it all.  If you don't know why this is better than doing TList.Sort, look up merge sort and compare it to bubble sort (what TList.Sort uses).  If after that you still don't know what this is about, then I think you should probably stop coding.

The sorting code is based off the code example here, since I was lazy and didn't feel like doing it myself: <a href="http://www.bsdg.org/SWAG/SORTING/0063.PAS.html" target="_blank">http://www.bsdg.org/SWAG/SORTING/0063.PAS.html[/url]  As such, it may be slightly hacky in the way it does things, since it's not made specifically for this list class.

* Bug fixed with me being stupid thanks to klepto.

Note: This is broken as far as I know, don't bother using.

Code :

Code: BlitzMax

1. Function MergeSort:TLink( head:TLink, num% )
2.        
3.         Local temp1:TLink, temp2:TLink
4.         Local ret:TLink
5.        
6.         If num <= 2 Then
7.                 If num = 1 Then
8.                         ret = head
9.                 Else
10.                         If head.Value().Compare(head._succ.Value()) < 0 Then
11.                                 ret = head
12.                         Else
13.                                 temp1 = head
14.                                 temp2 = head._succ
15.                                 temp1._pred = temp2
16.                                 temp2._succ = temp1
17.                                 temp1._succ = Null
18.                                 temp2._pred = Null
19.                                 ret = temp2
20.                         EndIf
21.                 EndIf
22.         Else
23.                 temp2 = head
24.                 Local n1%, n2%
25.                 n1 = num/2
26.                 n2 = num-n1
27.                
28.                 For Local idx:Int = 1 To n1-1
29.                         temp2 = temp2._succ
30.                 Next
31.                
32.                 temp1 = temp2
33.                 temp2 = temp2._succ
34.                 temp1._succ = Null
35.                 temp2._pred = Null
36.                 temp1 = head
37.                
38.                 temp1 = MergeSort( temp1, n1 )
39.                 temp2 = MergeSort( temp2, n2 )
40.                
41.                 Local l1:Int = False
42.                 ret = temp2
43.                
44.                 If temp1.Value().Compare(temp2.Value()) < 0 Then
45.                         ret = temp1
46.                         l1 = True
47.                 EndIf
48.                
49.                 While temp1 <> Null Or temp2 <> Null
50.                
51.                         If l1 Then
52.                                 While temp1._succ And temp1._succ.Value().Compare(temp2.Value()) < 0
53.                                         temp1 = temp1._succ
54.                                 Wend
55.                                 temp2._pred = temp1
56.                                 temp1 = temp1._succ
57.                                 temp2._pred._succ = temp2
58.                                 If temp1 = Null Then
59.                                         Exit
60.                                 EndIf
61.                         Else
62.                                 While temp2._succ And temp2._succ.Value().Compare(temp1.Value()) < 0
63.                                         temp2 = temp2._succ
64.                                 Wend
65.                                 temp1._pred = temp2
66.                                 temp2 = temp2._succ
67.                                 temp1._pred._succ = temp1
68.                                 If temp2 = Null Then
69.                                         Exit
70.                                 EndIf
71.                         EndIf
72.                        
73.                         l1 = Not l1
74.                        
75.                 Wend
76.         EndIf
77.        
78.         Return ret
79. End Function

Comments : none...