repos/tabletprog: modules/array.tp comparison

Add sort method to arrays

author	Michael Pavone <pavone@retrodev.com>
date	Sun, 22 Mar 2015 22:06:50 -0700
parents	bb4723fec05e
children	eb5f1fca9b78

comparison

equal deleted inserted replaced

-:3edd0169311a
+:fb54a3af9c86
 				idx <- l
 			}
 		}
 		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 {
 			str <- string: (get: 0)
 			idx <- 1

Mercurial > repos > tabletprog