Modernize and optimize DTQuickSortHEADmaster

1 files changed, 50 insertions, 44 deletions

diff --git a/DTQuickSort.c b/DTQuickSort.c
index 8f480ca..caa9369 100644
--- a/DTQuickSort.c
+++ b/DTQuickSort.c
@@ -1,15 +1,8 @@
-#strict 2
+#strict 3
 
 global func SortNumeric(int a, int b)
 {
-	if(a < b)
-	{
-		return -1;
-	}
-	else if(a > b)
-	{
-		return 1;
-	}
+	return a - b;
 }
 
 global func SortNumericInverse(int a, int b)
@@ -17,50 +10,63 @@ global func SortNumericInverse(int a, int b)
 	return -SortNumeric(a, b);
 }
 
-global func QSort(array& data, callback, callbackArgs) // WARNING: Can cause stack-overflow with too much data
+global func QSort(array& data, callback, callbackArgs)
 {
 	if(callback == true)
 	{
 		callback = GlobalCallback("SortNumericInverse");
 	}
-	QSort_Part(data, callback || GlobalCallback("SortNumeric"), 0, GetLength(data) - 1, callbackArgs);
-	return data;
-}
-
-global func QSort_Part(array& data, callback, int left, int right, callbackArgs)
-{
-	if(left < right)
+	else
 	{
-		// Partitioning
-		var pPos = RandomX(left, right);
-		var p = data[pPos];
-		var tmp;
-
-		tmp = data[pPos];
-		data[pPos] = data[right];
-		data[right] = tmp;
-		pPos = right;
-
-		var i = left - 1;
-		for(var j = left; j <= right; ++j)
+		callback ??= GlobalCallback("SortNumeric");
+	}
+	
+	// start of flattened recursive part
+	var stack = [[0, GetLength(data) - 1]];
+	
+	// stack pointer points to next empty slot
+	for(var stackPointer = 1; stackPointer > 0; )
+	{
+		var frame = stack[--stackPointer];
+		var left = frame[0];
+		var right = frame[1];
+		
+		if(left < right)
 		{
-			if(Call(callback, data[j],  p, callbackArgs) < 0)
+			// Partitioning
+			var pPos = RandomX(left, right);
+			var p = data[pPos];
+			var tmp;
+			
+			tmp = data[pPos];
+			data[pPos] = data[right];
+			data[right] = tmp;
+			pPos = right;
+			
+			var i = left - 1;
+			for(var j = left; j <= right; ++j)
 			{
-				++i;
-				tmp = data[i];
-				data[i] = data[j];
-				data[j] = tmp;
+				if(Call(callback, data[j],  p, callbackArgs) < 0)
+				{
+					++i;
+					tmp = data[i];
+					data[i] = data[j];
+					data[j] = tmp;
+				}
 			}
+			
+			++i;
+			
+			tmp = data[i];
+			data[i] = data[pPos];
+			data[pPos] = tmp;
+			// -----
+			
+			stack[stackPointer++] = [left, i - 1];
+			stack[stackPointer++] = [i + 1, right];
 		}
-
-		++i;
-
-		tmp = data[i];
-		data[i] = data[pPos];
-		data[pPos] = tmp;
-		// -----
-
-		QSort_Part(data, callback, left, i - 1, callbackArgs);
-		QSort_Part(data, callback, i + 1, right, callbackArgs);
 	}
+	// end of recursive part
+	
+	return data;
 }