diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -326,12 +326,23 @@ def bisect(ui, repo, rev=None, extra=Non
         return
 
     # actually bisect
-    node, changesets, good = hbisect.bisect(repo.changelog, state)
+    nodes, changesets, good = hbisect.bisect(repo.changelog, state)
     if changesets == 0:
-        ui.write(_("The first %s revision is:\n") % (good and "good" or "bad"))
         displayer = cmdutil.show_changeset(ui, repo, {})
-        displayer.show(changenode=node)
-    elif node is not None:
+        transition = (good and "good" or "bad")
+        if len(nodes) == 1:
+            # narrowed it down to a single revision
+            ui.write(_("The first %s revision is:\n") % transition)
+            displayer.show(changenode=nodes[0])
+        else:
+            # multiple possible revisions
+            ui.write(_("Due to skipped revisions, the first "
+                       "%s revision could be any of:\n") % transition)
+            for n in nodes:
+                displayer.show(changenode=n)
+    else:
+        assert len(nodes) == 1 # only a single node can be tested next
+        node = nodes[0]
         # compute the approximate number of remaining tests
         tests, size = 0, 2
         while size <= changesets:
diff --git a/mercurial/hbisect.py b/mercurial/hbisect.py
--- a/mercurial/hbisect.py
+++ b/mercurial/hbisect.py
@@ -12,6 +12,16 @@ from node import short
 import util
 
 def bisect(changelog, state):
+    """find the next node (if any) for testing during a bisect search.
+    returns a (nodes, number, good) tuple.
+
+    'nodes' is the final result of the bisect if 'number' is 0.
+    Otherwise 'number' indicates the remaining possible candidates for
+    the search and 'nodes' contains the next bisect target.
+    'good' is True if bisect is searching for a first good changeset, False
+    if searching for a first bad one.
+    """
+
     clparents = changelog.parentrevs
     skip = dict.fromkeys([changelog.rev(n) for n in state['skip']])
 
@@ -60,17 +70,20 @@ def bisect(changelog, state):
                         children[prev] = [rev]
                         visit.append(prev)
 
+    candidates.sort()
     # have we narrowed it down to one entry?
+    # or have all other possible candidates besides 'bad' have been skipped?
     tot = len(candidates)
-    if tot == 1:
-        return (bad, 0, good)
+    unskipped = [c for c in candidates if (c not in skip) and (c != badrev)]
+    if tot == 1 or not unskipped:
+        return ([changelog.node(rev) for rev in candidates], 0, good)
     perfect = tot / 2
 
     # find the best node to test
     best_rev = None
     best_len = -1
     poison = {}
-    for rev in util.sort(candidates):
+    for rev in candidates:
         if rev in poison:
             for c in children.get(rev, []):
                 poison[c] = True # poison children
@@ -102,4 +115,4 @@ def bisect(changelog, state):
     assert best_rev is not None
     best_node = changelog.node(best_rev)
 
-    return (best_node, tot, good)
+    return ([best_node], tot, good)
diff --git a/tests/test-bisect b/tests/test-bisect
--- a/tests/test-bisect
+++ b/tests/test-bisect
@@ -53,4 +53,18 @@ hg bisect -b tip || echo error
 hg bisect -r
 hg bisect -g null
 hg bisect -bU tip
-hg id
\ No newline at end of file
+hg id
+
+# reproduce AssertionError (issue1228 and issue1182)
+hg bisect -r
+hg bisect -b 4
+hg bisect -g 0
+hg bisect -s
+hg bisect -s
+hg bisect -s
+
+# reproduce non converging bisect (issue1182)
+hg bisect -r
+hg bisect -g 0
+hg bisect -b 2
+hg bisect -s
diff --git a/tests/test-bisect.out b/tests/test-bisect.out
--- a/tests/test-bisect.out
+++ b/tests/test-bisect.out
@@ -241,3 +241,43 @@ abort: Inconsistent state, 31:58c80a7c8a
 error
 Testing changeset 15:e7fa0811edb0 (32 changesets remaining, ~5 tests)
 5cd978ea5149
+Testing changeset 2:db07c04beaca (4 changesets remaining, ~2 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Testing changeset 1:5cd978ea5149 (4 changesets remaining, ~2 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Testing changeset 3:b53bea5e2fcb (4 changesets remaining, ~2 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Due to skipped revisions, the first bad revision could be any of:
+changeset:   1:5cd978ea5149
+user:        test
+date:        Thu Jan 01 00:00:01 1970 +0000
+summary:     msg 1
+
+changeset:   2:db07c04beaca
+user:        test
+date:        Thu Jan 01 00:00:02 1970 +0000
+summary:     msg 2
+
+changeset:   3:b53bea5e2fcb
+user:        test
+date:        Thu Jan 01 00:00:03 1970 +0000
+summary:     msg 3
+
+changeset:   4:9b2ba8336a65
+user:        test
+date:        Thu Jan 01 00:00:04 1970 +0000
+summary:     msg 4
+
+Testing changeset 1:5cd978ea5149 (2 changesets remaining, ~1 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Due to skipped revisions, the first bad revision could be any of:
+changeset:   1:5cd978ea5149
+user:        test
+date:        Thu Jan 01 00:00:01 1970 +0000
+summary:     msg 1
+
+changeset:   2:db07c04beaca
+user:        test
+date:        Thu Jan 01 00:00:02 1970 +0000
+summary:     msg 2
+
diff --git a/tests/test-bisect2 b/tests/test-bisect2
new file mode 100755
--- /dev/null
+++ b/tests/test-bisect2
@@ -0,0 +1,153 @@
+#!/bin/sh
+
+# The tests in test-bisect are done on a linear history.
+# Here the following repository history is used for testing:
+#
+#                     17
+#                      |
+#               18    16 
+#                 \  /
+#                  15
+#                 /  \
+#                /    \
+#              10     13
+#              / \     |
+#             /   \    |  14
+#        7   6     9  12 /
+#         \ / \    |   |/
+#          4   \   |  11
+#           \   \  |  /
+#            3   5 | /
+#             \ /  |/ 
+#              2   8
+#               \ /
+#                1
+#                |
+#                0
+
+set -e
+
+echo % init
+hg init
+
+echo % committing changes
+echo > a
+echo '0' >> a
+hg add a
+hg ci -m "0" -d "0 0"
+echo '1' >> a
+hg ci -m "1" -d "1 0"
+echo '2' >> a
+hg ci -m "2" -d "2 0"
+echo '3' >> a
+hg ci -m "3" -d "3 0"
+echo '4' >> a
+hg ci -m "4" -d "4 0"
+# create branch
+hg up -r 2
+echo '5' >> b
+hg add b
+hg ci -m "5" -d "5 0"
+
+# merge
+hg merge
+hg ci -m "merge 4,5" -d "6 0"
+
+# create branch
+hg up -r 4
+echo '7' > c
+hg add c
+hg ci -m "7" -d "7 0"
+
+# create branch
+hg up -r 1
+echo '8' > d
+hg add d
+hg ci -m "8" -d "8 0"
+echo '9' >> d
+hg ci -m "9" -d "9 0"
+
+# merge
+hg merge -r 6
+hg ci -m "merge 6,9" -d "10 0"
+
+# create branch
+hg up -r 8
+echo '11' > e
+hg add e
+hg ci -m "11" -d "11 0"
+echo '12' >> e
+hg ci -m "12" -d "12 0"
+echo '13' >> e
+hg ci -m "13" -d "13 0"
+
+# create branch
+hg up -r 11
+echo '14' > f
+hg add f
+hg ci -m "14" -d "14 0"
+
+# merge
+hg up -r 13 -C
+hg merge -r 10
+hg ci -m "merge 10,13" -d "15 0"
+echo '16' >> e
+hg ci -m "16" -d "16 0"
+echo '17' >> e
+hg ci -m "17" -d "17 0"
+
+# create branch
+hg up -r 15
+echo '18' >> e
+hg ci -m "18" -d "18 0"
+
+
+echo % log
+hg log
+
+echo % hg up -C
+hg up -C
+
+echo % complex bisect test 1  # first bad rev is 9
+hg bisect -r
+hg bisect -g 0
+hg bisect -b 17   # -> update to rev 6
+hg bisect -g      # -> update to rev 13
+hg bisect -s      # -> update to rev 10
+hg bisect -b      # -> update to rev 8
+hg bisect -g      # -> update to rev 9
+hg bisect -b
+
+echo % complex bisect test 2  # first good rev is 13
+hg bisect -r
+hg bisect -g 18
+hg bisect -b 1    # -> update to rev 6
+hg bisect -s      # -> update to rev 10
+hg bisect -b      # -> update to rev 12
+hg bisect -b      # -> update to rev 13
+hg bisect -g
+
+echo % complex bisect test 3  
+# first bad rev is 15 
+# 10,9,13 are skipped an might be the first bad revisions as well
+hg bisect -r
+hg bisect -g 1
+hg bisect -b 16   # -> update to rev 6
+hg bisect -g      # -> update to rev 13
+hg bisect -s      # -> update to rev 10
+hg bisect -s      # -> update to rev 12
+hg bisect -g      # -> update to rev 9
+hg bisect -s      # -> update to rev 15
+hg bisect -b
+
+echo % complex bisect test 4
+# first good revision is 17
+# 15,16 are skipped an might be the first good revisions as well
+hg bisect -r
+hg bisect -g 17
+hg bisect -b 8    # -> update to rev 10
+hg bisect -b      # -> update to rev 13
+hg bisect -b      # -> update to rev 15
+hg bisect -s      # -> update to rev 16
+hg bisect -s
+
diff --git a/tests/test-bisect2.out b/tests/test-bisect2.out
new file mode 100644
--- /dev/null
+++ b/tests/test-bisect2.out
@@ -0,0 +1,229 @@
+% init
+% committing changes
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+created new head
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+(branch merge, don't forget to commit)
+0 files updated, 0 files merged, 1 files removed, 0 files unresolved
+created new head
+1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+created new head
+2 files updated, 0 files merged, 0 files removed, 0 files unresolved
+(branch merge, don't forget to commit)
+2 files updated, 0 files merged, 1 files removed, 0 files unresolved
+created new head
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+created new head
+1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+3 files updated, 0 files merged, 0 files removed, 0 files unresolved
+(branch merge, don't forget to commit)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+created new head
+% log
+changeset:   18:d42e18c7bc9b
+tag:         tip
+parent:      15:857b178a7cf3
+user:        test
+date:        Thu Jan 01 00:00:18 1970 +0000
+summary:     18
+
+changeset:   17:228c06deef46
+user:        test
+date:        Thu Jan 01 00:00:17 1970 +0000
+summary:     17
+
+changeset:   16:609d82a7ebae
+user:        test
+date:        Thu Jan 01 00:00:16 1970 +0000
+summary:     16
+
+changeset:   15:857b178a7cf3
+parent:      13:b0a32c86eb31
+parent:      10:429fcd26f52d
+user:        test
+date:        Thu Jan 01 00:00:15 1970 +0000
+summary:     merge 10,13
+
+changeset:   14:faa450606157
+parent:      11:82ca6f06eccd
+user:        test
+date:        Thu Jan 01 00:00:14 1970 +0000
+summary:     14
+
+changeset:   13:b0a32c86eb31
+user:        test
+date:        Thu Jan 01 00:00:13 1970 +0000
+summary:     13
+
+changeset:   12:9f259202bbe7
+user:        test
+date:        Thu Jan 01 00:00:12 1970 +0000
+summary:     12
+
+changeset:   11:82ca6f06eccd
+parent:      8:dab8161ac8fc
+user:        test
+date:        Thu Jan 01 00:00:11 1970 +0000
+summary:     11
+
+changeset:   10:429fcd26f52d
+parent:      9:3c77083deb4a
+parent:      6:a214d5d3811a
+user:        test
+date:        Thu Jan 01 00:00:10 1970 +0000
+summary:     merge 6,9
+
+changeset:   9:3c77083deb4a
+user:        test
+date:        Thu Jan 01 00:00:09 1970 +0000
+summary:     9
+
+changeset:   8:dab8161ac8fc
+parent:      1:4ca5088da217
+user:        test
+date:        Thu Jan 01 00:00:08 1970 +0000
+summary:     8
+
+changeset:   7:50c76098bbf2
+parent:      4:5c668c22234f
+user:        test
+date:        Thu Jan 01 00:00:07 1970 +0000
+summary:     7
+
+changeset:   6:a214d5d3811a
+parent:      5:385a529b6670
+parent:      4:5c668c22234f
+user:        test
+date:        Thu Jan 01 00:00:06 1970 +0000
+summary:     merge 4,5
+
+changeset:   5:385a529b6670
+parent:      2:051e12f87bf1
+user:        test
+date:        Thu Jan 01 00:00:05 1970 +0000
+summary:     5
+
+changeset:   4:5c668c22234f
+user:        test
+date:        Thu Jan 01 00:00:04 1970 +0000
+summary:     4
+
+changeset:   3:0950834f0a9c
+user:        test
+date:        Thu Jan 01 00:00:03 1970 +0000
+summary:     3
+
+changeset:   2:051e12f87bf1
+user:        test
+date:        Thu Jan 01 00:00:02 1970 +0000
+summary:     2
+
+changeset:   1:4ca5088da217
+user:        test
+date:        Thu Jan 01 00:00:01 1970 +0000
+summary:     1
+
+changeset:   0:33b1f9bc8bc5
+user:        test
+date:        Thu Jan 01 00:00:00 1970 +0000
+summary:     0
+
+% hg up -C
+0 files updated, 0 files merged, 0 files removed, 0 files unresolved
+% complex bisect test 1
+Testing changeset 6:a214d5d3811a (15 changesets remaining, ~3 tests)
+0 files updated, 0 files merged, 2 files removed, 0 files unresolved
+Testing changeset 13:b0a32c86eb31 (9 changesets remaining, ~3 tests)
+3 files updated, 0 files merged, 1 files removed, 0 files unresolved
+Testing changeset 10:429fcd26f52d (9 changesets remaining, ~3 tests)
+3 files updated, 0 files merged, 1 files removed, 0 files unresolved
+Testing changeset 8:dab8161ac8fc (3 changesets remaining, ~1 tests)
+2 files updated, 0 files merged, 1 files removed, 0 files unresolved
+Testing changeset 9:3c77083deb4a (2 changesets remaining, ~1 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+The first bad revision is:
+changeset:   9:3c77083deb4a
+user:        test
+date:        Thu Jan 01 00:00:09 1970 +0000
+summary:     9
+
+% complex bisect test 2
+Testing changeset 6:a214d5d3811a (13 changesets remaining, ~3 tests)
+2 files updated, 0 files merged, 1 files removed, 0 files unresolved
+Testing changeset 10:429fcd26f52d (13 changesets remaining, ~3 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Testing changeset 12:9f259202bbe7 (5 changesets remaining, ~2 tests)
+3 files updated, 0 files merged, 1 files removed, 0 files unresolved
+Testing changeset 13:b0a32c86eb31 (3 changesets remaining, ~1 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+The first good revision is:
+changeset:   13:b0a32c86eb31
+user:        test
+date:        Thu Jan 01 00:00:13 1970 +0000
+summary:     13
+
+% complex bisect test 3
+Testing changeset 6:a214d5d3811a (13 changesets remaining, ~3 tests)
+2 files updated, 0 files merged, 2 files removed, 0 files unresolved
+Testing changeset 13:b0a32c86eb31 (8 changesets remaining, ~3 tests)
+3 files updated, 0 files merged, 1 files removed, 0 files unresolved
+Testing changeset 10:429fcd26f52d (8 changesets remaining, ~3 tests)
+3 files updated, 0 files merged, 1 files removed, 0 files unresolved
+Testing changeset 12:9f259202bbe7 (8 changesets remaining, ~3 tests)
+3 files updated, 0 files merged, 1 files removed, 0 files unresolved
+Testing changeset 9:3c77083deb4a (5 changesets remaining, ~2 tests)
+1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+Testing changeset 15:857b178a7cf3 (5 changesets remaining, ~2 tests)
+3 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Due to skipped revisions, the first bad revision could be any of:
+changeset:   9:3c77083deb4a
+user:        test
+date:        Thu Jan 01 00:00:09 1970 +0000
+summary:     9
+
+changeset:   10:429fcd26f52d
+parent:      9:3c77083deb4a
+parent:      6:a214d5d3811a
+user:        test
+date:        Thu Jan 01 00:00:10 1970 +0000
+summary:     merge 6,9
+
+changeset:   13:b0a32c86eb31
+user:        test
+date:        Thu Jan 01 00:00:13 1970 +0000
+summary:     13
+
+changeset:   15:857b178a7cf3
+parent:      13:b0a32c86eb31
+parent:      10:429fcd26f52d
+user:        test
+date:        Thu Jan 01 00:00:15 1970 +0000
+summary:     merge 10,13
+
+% complex bisect test 4
+Testing changeset 10:429fcd26f52d (13 changesets remaining, ~3 tests)
+0 files updated, 0 files merged, 1 files removed, 0 files unresolved
+Testing changeset 13:b0a32c86eb31 (6 changesets remaining, ~2 tests)
+3 files updated, 0 files merged, 1 files removed, 0 files unresolved
+Testing changeset 15:857b178a7cf3 (3 changesets remaining, ~1 tests)
+3 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Testing changeset 16:609d82a7ebae (3 changesets remaining, ~1 tests)
+1 files updated, 0 files merged, 0 files removed, 0 files unresolved
+Due to skipped revisions, the first good revision could be any of:
+changeset:   15:857b178a7cf3
+parent:      13:b0a32c86eb31
+parent:      10:429fcd26f52d
+user:        test
+date:        Thu Jan 01 00:00:15 1970 +0000
+summary:     merge 10,13
+
+changeset:   16:609d82a7ebae
+user:        test
+date:        Thu Jan 01 00:00:16 1970 +0000
+summary:     16
+
+changeset:   17:228c06deef46
+user:        test
+date:        Thu Jan 01 00:00:17 1970 +0000
+summary:     17
+