1 files changed, 38 insertions, 7 deletions
diff --git a/lib/pure/algorithm.nim b/lib/pure/algorithm.nim
index 0eafb316a..ac18ae420 100644
--- a/lib/pure/algorithm.nim
+++ b/lib/pure/algorithm.nim
@@ -99,16 +99,13 @@ proc lowerBound*[T](a: openArray[T], key: T, cmp: proc(x,y: T): int {.closure.})
   ##   arr.insert(4, arr.lowerBound(4))
   ## `after running the above arr is `[1,2,3,4,5,6,7,8,9]`
   result = a.low
-  var pos = result
-  var count, step: int
-  count = a.high - a.low + 1
+  var count = a.high - a.low + 1
+  var step, pos: int
   while count != 0:
-    pos = result
     step = count div 2
-    pos += step
+    pos = result + step
     if cmp(a[pos], key) < 0:
-      pos.inc
-      result = pos
+      result = pos + 1
       count -= step + 1
     else:
       count = step
@@ -240,6 +237,17 @@ template sortedByIt*(seq1, op: expr): expr =
     result = cmp(a, b))
   result
 
+proc isSorted*[T](a: openarray[T],
+                 cmp: proc(x, y: T): int {.closure.},
+                 order = SortOrder.Ascending): bool =
+  ## Checks to see whether `a` is already sorted in `order`
+  ## using `cmp` for the comparison. Parameters identical
+  ## to `sort`
+  result = true
+  for i in 0..<len(a)-1:
+    if cmp(a[i],a[i+1]) * order > 0:
+      return false
+
 proc product*[T](x: openArray[seq[T]]): seq[seq[T]] =
   ## produces the Cartesian product of the array. Warning: complexity
   ## may explode.
@@ -331,3 +339,26 @@ proc prevPermutation*[T](x: var openarray[T]): bool {.discardable.} =
   swap x[i-1], x[j]
 
   result = true
+
+when isMainModule:
+  # Tests for lowerBound
+  var arr = @[1,2,3,5,6,7,8,9]
+  assert arr.lowerBound(0) == 0
+  assert arr.lowerBound(4) == 3
+  assert arr.lowerBound(5) == 3
+  assert arr.lowerBound(10) == 8
+  arr = @[1,5,10]
+  assert arr.lowerBound(4) == 1
+  assert arr.lowerBound(5) == 1
+  assert arr.lowerBound(6) == 2
+  # Tests for isSorted
+  var srt1 = [1,2,3,4,4,4,4,5]
+  var srt2 = ["iello","hello"]
+  var srt3 = [1.0,1.0,1.0]
+  var srt4 = []
+  assert srt1.isSorted(cmp) == true
+  assert srt2.isSorted(cmp) == false
+  assert srt3.isSorted(cmp) == true
+  var srtseq = newSeq[int]()
+  assert srtseq.isSorted(cmp) == true
+