# HG changeset patch
# User Michael Pavone <pavone@retrodev.com>
# Date 1427087210 25200
# Node ID fb54a3af9c86de78364b5c40e11dee8e99c22330
# Parent  3edd0169311a337cf8dbacfbf1b7d6c7586a21fe
Add sort method to arrays

diff -r 3edd0169311a -r fb54a3af9c86 modules/array.tp
--- a/modules/array.tp	Sun Mar 22 19:10:32 2015 -0700
+++ b/modules/array.tp	Sun Mar 22 22:06:50 2015 -0700
@@ -129,6 +129,66 @@
 		}
 		ret
 	}
+	
+	sort <- {
+		n <- length
+		tmp <- #[]
+		tmp resize: n
+		while: { (tmp length) < n} do: {
+			tmp append: false
+		}
+		src <- self
+		dst <- tmp
+		
+		merge <- :lStart rStart rEnd {
+			dstIdx <- lStart
+			left <- lStart
+			right <- rStart
+			
+			while: { dstIdx < rEnd } do: {
+				if: left < rStart && (right >= rEnd || (src get: left) <= (src get: right)) {
+					dst set: dstIdx (src get: left)
+					left <- left + 1
+				} else: {
+					dst set: dstIdx (src get: right)
+					right <- right + 1
+				}
+				dstIdx <- dstIdx + 1
+			}
+		}
+		
+		needsCopy? <- false
+		subSize <- 1
+		while: { subSize < n} do: {
+			group <- subSize * 2
+			i <- 0
+			while: { i < n} do: {
+				right <- i + subSize
+				end <- i + group
+				if: right > n {
+					right <- n
+					end <- n
+				} else: {
+					if: end > n {
+						end <- n
+					}
+				}
+				merge: i right end
+				i <- i + group
+			}
+			tmp <- dst
+			dst <- src
+			src <- tmp
+			needsCopy? <- not: needsCopy?
+		
+			subSize <- subSize + subSize
+		}
+		if: needsCopy? {
+			foreach: src :index val {
+				self set: index val
+			}
+		}
+	}
 
 	join <- :sep {
 		if: length > 0 {
diff -r 3edd0169311a -r fb54a3af9c86 samples/sort.tp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/samples/sort.tp	Sun Mar 22 22:06:50 2015 -0700
@@ -0,0 +1,16 @@
+#{
+	main <- {
+		a <- #[1 2 3 4 5 6 7 8 9]
+		b <- #[9 8 7 6 5 4 3 2 1]
+		c <- #[1 3 5 7 9 2 4 6 8 10]
+		d <- #[10 8 6 4 2 9 7 5 3 1]
+		a sort
+		print: (a join: " ") . "\n"
+		b sort
+		print: (b join: " ") . "\n"
+		c sort
+		print: (c join: " ") . "\n"
+		d sort
+		print: (d join: " ") . "\n"
+	}
+}
\ No newline at end of file