Here's a patch to replace the current bubble sort sorting algorithm in brl.mod/linkedlist.mod/linkedlist.bmx with the merge sort algorithm. This is, more or less, much faster than the original.
Edit to BRL: Also, your patterns for matching e-mail addresses and such are broken or in the wrong order.
From 205f13af7b2dfb461478f99bf4505414b44382c3 Mon Sep 17 00:00:00 2001
From: Noel Cower <ncower@...;
Date: Sun, 18 Jan 2009 12:11:35 -0800
Subject: [PATCH] Rewritten sort method to use merge sort algorithm
---
linkedlist.bmx | 123 ++++++++++++++++++++++++++++++++++++++++++++-----------
1 files changed, 98 insertions(+), 25 deletions(-)
diff --git a/linkedlist.bmx b/linkedlist.bmx
index ed16e1e..8dc00c8 100644
--- a/linkedlist.bmx
+++ b/linkedlist.bmx
@@ -346,33 +346,106 @@ Type TList Extends TData
bbdoc: Sort a list in either ascending (default) or decending order.
about: User types should implement a Compare method in order to be sorted.
End Rem
- Method Sort( ascending=True,compareFunc( o1:Object,o2:Object )=CompareObjects )
- Local term:TLink=_head
- Repeat
- Local link:TLink=_head._succ
- Local sorted=True
- Repeat
- Local succ:TLink=link._succ
- If succ=term Exit
- Local cc=CompareFunc( link._value,succ._value ) 'link._value.Compare( succ._value )
- If (cc>0 And ascending) Or (cc<0 And Not ascending)
- Local link_pred:TLink=link._pred
- Local succ_succ:TLink=succ._succ
- link_pred._succ=succ
- succ._succ=link
- succ._pred=link_pred
- link._succ=succ_succ
- link._pred=succ
- succ_succ._pred=link
- sorted=False
+ Method Sort( ascending=True, compareFunc( o1:Object, o2:Object )=CompareObjects )
+ If _head._succ = _head._pred Then
+ Return ' List is either empty or only has one item
+ EndIf
+
+ Local head:TLink = _head._succ
+ Local tail:TLink = _head._pred
+ Local cnt:Int = Count()
+ head._pred = Null
+ tail._succ = Null
+ head = TList._rec_sort( head, cnt, compareFunc )
+ tail = head
+ While tail._succ
+ tail = tail._succ
+ Wend
+ head._pred = _head; _head._succ = head
+ tail._succ = _head; _head._pred = tail
+
+ ' Reverse if not ascending
+ If Not ascending Then
+ Reverse()
+ EndIf
+ End Method
+
+ Function _rec_sort:TLink( head:TLink, num%, compareFunc( o1:Object, o2:Object ) ) NoDebug
+ Local temp1:TLink, temp2:TLink
+ Local ret:TLink
+
+ If num <= 2 Then
+ If num = 1 Then
+ ret = head
+ Else
+ If compareFunc( head._value, head._succ._value ) < 0 Then
+ ret = head
Else
- link=succ
+ temp1 = head
+ temp2 = head._succ
+ temp1._pred = temp2
+ temp2._succ = temp1
+ temp1._succ = Null
+ temp2._pred = Null
+ ret = temp2
EndIf
- Forever
- If sorted Return
- term=link
- Forever
- End Method
+ EndIf
+ Else
+ temp2 = head
+ Local n1%, n2%
+ n1 = num/2
+ n2 = num-n1
+
+ For Local idx:Int = 1 To n1-1
+ temp2 = temp2._succ
+ Next
+
+ temp1 = temp2
+ temp2 = temp2._succ
+ temp1._succ = Null
+ temp2._pred = Null
+ temp1 = head
+
+ temp1 = TList._rec_sort( temp1, n1, compareFunc )
+ temp2 = TList._rec_sort( temp2, n2, compareFunc )
+
+ Local l1:Int = False
+ ret = temp2
+
+ If compareFunc( temp1._value, temp2._value ) < 0 Then
+ ret = temp1
+ l1 = True
+ EndIf
+
+ While temp1 <> Null Or temp2 <> Null
+ If l1 Then
+ While temp1._succ And compareFunc(temp1._succ._value, temp2._value) < 0
+ temp1 = temp1._succ
+ Wend
+ temp2._pred = temp1
+ temp1 = temp1._succ
+ temp2._pred._succ = temp2
+ If temp1 = Null Then
+ Exit
+ EndIf
+ Else
+ While temp2._succ And compareFunc(temp2._succ._value, temp1._value) < 0
+ temp2 = temp2._succ
+ Wend
+ temp1._pred = temp2
+ temp2 = temp2._succ
+ temp1._pred._succ = temp1
+ If temp2 = Null Then
+ Exit
+ EndIf
+ EndIf
+
+ l1 = Not l1
+ Wend
+ EndIf
+
+ Return ret
+ End Function
Method ObjectEnumerator:TListEnum()
Local enum:TListEnum=New TListEnum
--
1.6.1.76.gc123b
| 
