Mercurial > repos > tabletprog
diff modules/array.tp @ 322:fb54a3af9c86
Add sort method to arrays
author | Michael Pavone <pavone@retrodev.com> |
---|---|
date | Sun, 22 Mar 2015 22:06:50 -0700 |
parents | bb4723fec05e |
children | eb5f1fca9b78 |
line wrap: on
line diff
--- 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 {