diff --git a/site/versions/master/docs/skylark/concepts.md b/site/versions/master/docs/skylark/concepts.md
index 2d5430f..59b3d2e 100644
--- a/site/versions/master/docs/skylark/concepts.md
+++ b/site/versions/master/docs/skylark/concepts.md
@@ -199,6 +199,12 @@
   declaration. However, it is fine to define `f()` before `g()`, even if `f()`
   calls `g()`.
 
+* The order comparison operators (<, <=, >=, >) are not defined across different
+  types of values, e.g., you can't compare `5 < 'foo'` (however you still can
+  compare them using == or !=). This is a difference with Python 2, but
+  consistent with Python 3. Note that this means you are unable to sort lists
+  that contain mixed types of values.
+
 The following Python features are not supported:
 
 * `class` (see [`struct`](lib/globals.html#struct) function)
@@ -244,11 +250,6 @@
 *   The `|` operator is defined for depsets as a synonym for `+`. This will be
     going away; use `+` instead.
 
-*   The order comparison operators (<, <=, >=, >) are currently defined across
-    different types of values, e.g., you can write `5 < 'foo'`. This will be an
-    error, just like in Python 3. Note that this means you will be unable to
-    sort lists that contain mixed types of values.
-
 *   The structure of the set that you get back from using the `+` or `|`
     operator is changing. Previously `a + b`, where `a` is a set, would include
     as its direct items all of `a`'s direct items. Under the upcoming way, the
diff --git a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
index 29b9902..4b7adbc 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/Artifact.java
@@ -31,6 +31,7 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
 import com.google.devtools.build.lib.syntax.EvalUtils;
+import com.google.devtools.build.lib.syntax.EvalUtils.ComparisonException;
 import com.google.devtools.build.lib.syntax.Printer;
 import com.google.devtools.build.lib.util.FileType;
 import com.google.devtools.build.lib.util.Preconditions;
@@ -135,7 +136,7 @@
     if (o instanceof Artifact) {
       return EXEC_PATH_COMPARATOR.compare(this, (Artifact) o);
     }
-    return EvalUtils.compareByClass(this, o);
+    throw new ComparisonException("Cannot compare artifact with " + EvalUtils.getDataTypeName(o));
   }
 
 
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
index 7c0af2c..1580fb4 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/EvalUtils.java
@@ -72,20 +72,44 @@
           o1 = SkylarkType.convertToSkylark(o1, /*env=*/ null);
           o2 = SkylarkType.convertToSkylark(o2, /*env=*/ null);
 
-          if (o1 instanceof ClassObject && o2 instanceof ClassObject) {
-            throw new ComparisonException("Cannot compare structs");
-          }
-          if (o1 instanceof SkylarkNestedSet && o2 instanceof SkylarkNestedSet) {
-            throw new ComparisonException("Cannot compare depsets");
-          }
           if (o1 instanceof SkylarkList
               && o2 instanceof SkylarkList
               && ((SkylarkList) o1).isTuple() == ((SkylarkList) o2).isTuple()) {
             return compareLists((SkylarkList) o1, (SkylarkList) o2);
           }
+          if (!o1.getClass().equals(o2.getClass())) {
+            throw new ComparisonException(
+                "Cannot compare " + getDataTypeName(o1) + " with " + getDataTypeName(o2));
+          }
+
+          if (o1 instanceof ClassObject) {
+            throw new ComparisonException("Cannot compare structs");
+          }
+          if (o1 instanceof SkylarkNestedSet) {
+            throw new ComparisonException("Cannot compare depsets");
+          }
           try {
             return ((Comparable<Object>) o1).compareTo(o2);
           } catch (ClassCastException e) {
+            throw new ComparisonException(
+                "Cannot compare " + getDataTypeName(o1) + " with " + getDataTypeName(o2));
+          }
+        }
+      };
+
+  /**
+   * Legacy Skylark comparator.
+   *
+   * <p>Falls back to comparing by class if objects are not comparable otherwise.
+   */
+  public static final Ordering<Object> SAFE_SKYLARK_COMPARATOR =
+      new Ordering<Object>() {
+        @Override
+        @SuppressWarnings("unchecked")
+        public int compare(Object o1, Object o2) {
+          try {
+            return SKYLARK_COMPARATOR.compare(o1, o2);
+          } catch (ComparisonException e) {
             return compareByClass(o1, o2);
           }
         }
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
index 77c708c..3a01f76 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/MethodLibrary.java
@@ -28,6 +28,7 @@
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkSignature;
+import com.google.devtools.build.lib.syntax.EvalUtils.ComparisonException;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.syntax.Type.ConversionException;
@@ -992,15 +993,20 @@
         "Returns the smallest one of all given arguments. "
             + "If only one argument is provided, it must be a non-empty iterable.",
     extraPositionals =
-      @Param(name = "args", type = SkylarkList.class, doc = "The elements to be checked."),
+        @Param(name = "args", type = SkylarkList.class, doc = "The elements to be checked."),
     useLocation = true
   )
-  private static final BuiltinFunction min = new BuiltinFunction("min") {
-    @SuppressWarnings("unused") // Accessed via Reflection.
-    public Object invoke(SkylarkList<?> args, Location loc) throws EvalException {
-      return findExtreme(args, EvalUtils.SKYLARK_COMPARATOR.reverse(), loc);
-    }
-  };
+  private static final BuiltinFunction min =
+      new BuiltinFunction("min") {
+        @SuppressWarnings("unused") // Accessed via Reflection.
+        public Object invoke(SkylarkList<?> args, Location loc) throws EvalException {
+          try {
+            return findExtreme(args, EvalUtils.SKYLARK_COMPARATOR.reverse(), loc);
+          } catch (ComparisonException e) {
+            throw new EvalException(loc, e);
+          }
+        }
+      };
 
   @SkylarkSignature(
     name = "max",
@@ -1009,15 +1015,20 @@
         "Returns the largest one of all given arguments. "
             + "If only one argument is provided, it must be a non-empty iterable.",
     extraPositionals =
-      @Param(name = "args", type = SkylarkList.class, doc = "The elements to be checked."),
+        @Param(name = "args", type = SkylarkList.class, doc = "The elements to be checked."),
     useLocation = true
   )
-  private static final BuiltinFunction max = new BuiltinFunction("max") {
-    @SuppressWarnings("unused") // Accessed via Reflection.
-    public Object invoke(SkylarkList<?> args, Location loc) throws EvalException {
-      return findExtreme(args, EvalUtils.SKYLARK_COMPARATOR, loc);
-    }
-  };
+  private static final BuiltinFunction max =
+      new BuiltinFunction("max") {
+        @SuppressWarnings("unused") // Accessed via Reflection.
+        public Object invoke(SkylarkList<?> args, Location loc) throws EvalException {
+          try {
+            return findExtreme(args, EvalUtils.SKYLARK_COMPARATOR, loc);
+          } catch (ComparisonException e) {
+            throw new EvalException(loc, e);
+          }
+        }
+      };
 
   /**
    * Returns the maximum element from this list, as determined by maxOrdering.
@@ -1084,8 +1095,8 @@
     name = "sorted",
     returnType = MutableList.class,
     doc =
-        "Sort a collection. Elements are sorted first by their type, "
-            + "then by their value (in ascending order).",
+        "Sort a collection. Elements should all belong to the same orderable type, they are sorted "
+            + "by their value (in ascending order).",
     parameters = {@Param(name = "self", type = Object.class, doc = "This collection.")},
     useLocation = true,
     useEnvironment = true
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/Printer.java b/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
index af6515f..730a830 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/Printer.java
@@ -171,7 +171,9 @@
    */
   private static <K, V> Set<Map.Entry<K, V>> getSortedEntrySet(Map<K, V> dict) {
     if (!(dict instanceof SortedMap<?, ?>)) {
-      Map<K, V> tmp = new TreeMap<>(EvalUtils.SKYLARK_COMPARATOR);
+      // TODO(bazel-team): Dict keys should not be sorted, because comparison of objects of
+      // potentially different types is not supported anymore in Skylark.
+      Map<K, V> tmp = new TreeMap<>(EvalUtils.SAFE_SKYLARK_COMPARATOR);
       tmp.putAll(dict);
       dict = tmp;
     }
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java b/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
index 59daa25..e0b48b8 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/EvalUtilsTest.java
@@ -22,11 +22,13 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+import com.google.devtools.build.lib.packages.SkylarkClassObjectConstructor;
 import com.google.devtools.build.lib.skylarkinterface.SkylarkModule;
+import com.google.devtools.build.lib.syntax.EvalUtils.ComparisonException;
 import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
 import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
 import com.google.devtools.build.lib.syntax.util.EvaluationTestCase;
-import java.util.TreeMap;
+import org.junit.Assert;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -115,21 +117,43 @@
 
   @Test
   public void testComparatorWithDifferentTypes() throws Exception {
-    TreeMap<Object, Object> map = new TreeMap<>(EvalUtils.SKYLARK_COMPARATOR);
-    map.put(2, 3);
-    map.put("1", 5);
-    map.put(42, 4);
-    map.put("test", 7);
-    map.put(-1, 2);
-    map.put("4", 6);
-    map.put(true, 1);
-    map.put(Runtime.NONE, 0);
+    Object[] objects = {
+        "1",
+        2,
+        true,
+        Runtime.NONE,
+        SkylarkList.Tuple.of(1, 2, 3),
+        SkylarkList.Tuple.of("1", "2", "3"),
+        SkylarkList.MutableList.of(env, 1, 2, 3),
+        SkylarkList.MutableList.of(env, "1", "2", "3"),
+        SkylarkDict.of(env, "key", 123),
+        SkylarkDict.of(env, 123, "value"),
+        NestedSetBuilder.stableOrder().add(1).add(2).add(3).build(),
+        SkylarkClassObjectConstructor.STRUCT.create(
+            ImmutableMap.of("key", (Object) "value"), "no field %s"),
+    };
 
-    int expected = 0;
-    // Expected order of keys is NoneType -> Double -> Integers -> Strings
-    for (Object obj : map.values()) {
-      assertThat(obj).isEqualTo(expected);
-      ++expected;
+    for (int i = 0; i < objects.length; ++i) {
+      for (int j = 0; j < objects.length; ++j) {
+        if (i != j) {
+          try {
+            EvalUtils.SKYLARK_COMPARATOR.compare(objects[i], objects[j]);
+            Assert.fail("Shouldn't have compared different types");
+          } catch (ComparisonException e) {
+            // expected
+          }
+        }
+      }
+    }
+  }
+
+  @Test
+  public void testComparatorWithNones() throws Exception {
+    try {
+      EvalUtils.SKYLARK_COMPARATOR.compare(Runtime.NONE, Runtime.NONE);
+      Assert.fail("Shouldn't have compared nones");
+    } catch (ComparisonException e) {
+      // expected
     }
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
index 3181041..1d93eb9 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/MethodLibraryTest.java
@@ -89,9 +89,8 @@
   @Test
   public void testMinWithDifferentTypes() throws Exception {
     new BothModesTest()
-        .testStatement("min(1, '2', True)", true)
-        .testStatement("min([1, '2', True])", true)
-        .testStatement("min(None, 1, 'test')", Runtime.NONE);
+        .testIfExactError("Cannot compare int with string", "min(1, '2', True)")
+        .testIfExactError("Cannot compare int with string", "min([1, '2', True])");
   }
 
   @Test
@@ -143,9 +142,8 @@
   @Test
   public void testMaxWithDifferentTypes() throws Exception {
     new BothModesTest()
-        .testStatement("max(1, '2', True)", "2")
-        .testStatement("max([1, '2', True])", "2")
-        .testStatement("max(None, 1, 'test')", "test");
+        .testIfExactError("Cannot compare int with string", "max(1, '2', True)")
+        .testIfExactError("Cannot compare int with string", "max([1, '2', True])");
   }
 
   @Test
@@ -1105,9 +1103,9 @@
         .testEval("sorted([[1], [], [2], [1, 2]])", "[[], [1], [1, 2], [2]]")
         .testEval("sorted([True, False, True])", "[False, True, True]")
         .testEval("sorted(['a','x','b','z'])", "[\"a\", \"b\", \"x\", \"z\"]")
-        .testEval("sorted([sorted, sorted])", "[sorted, sorted]")
         .testEval("sorted({1: True, 5: True, 4: False})", "[1, 4, 5]")
-        .testEval("sorted(depset([1, 5, 4]))", "[1, 4, 5]");
+        .testEval("sorted(depset([1, 5, 4]))", "[1, 4, 5]")
+        .testIfExactError("Cannot compare function with function", "sorted([sorted, sorted])");
   }
 
   @Test