diff --git a/Lib/test/test_sort.py b/Lib/test/test_sort.py
index f2f53cb..41de4b6 100644
--- a/Lib/test/test_sort.py
+++ b/Lib/test/test_sort.py
@@ -373,6 +373,11 @@
         check_against_PyObject_RichCompareBool(self, [float('nan')]*100)
         check_against_PyObject_RichCompareBool(self, [float('nan') for
                                                       _ in range(100)])
+
+    def test_not_all_tuples(self):
+        self.assertRaises(TypeError, [(1.0, 1.0), (False, "A"), 6].sort)
+        self.assertRaises(TypeError, [('a', 1), (1, 'a')].sort)
+        self.assertRaises(TypeError, [(1, 'a'), ('a', 1)].sort)
 #==============================================================================
 
 if __name__ == "__main__":
diff --git a/Misc/NEWS.d/next/Core and Builtins/2019-03-07-13-05-43.bpo-36218.dZemNt.rst b/Misc/NEWS.d/next/Core and Builtins/2019-03-07-13-05-43.bpo-36218.dZemNt.rst
new file mode 100644
index 0000000..ab6d207
--- /dev/null
+++ b/Misc/NEWS.d/next/Core and Builtins/2019-03-07-13-05-43.bpo-36218.dZemNt.rst
@@ -0,0 +1,2 @@
+Fix a segfault occuring when sorting a list of heterogeneous values. Patch
+contributed by Rémi Lapeyre and Elliot Gorokhovsky.
\ No newline at end of file
diff --git a/Objects/listobject.c b/Objects/listobject.c
index 7dc68a7..d795f66 100644
--- a/Objects/listobject.c
+++ b/Objects/listobject.c
@@ -2250,19 +2250,28 @@
 
             if (key->ob_type != key_type) {
                 keys_are_all_same_type = 0;
-                break;
+                /* If keys are in tuple we must loop over the whole list to make
+                   sure all items are tuples */
+                if (!keys_are_in_tuples) {
+                    break;
+                }
             }
 
-            if (key_type == &PyLong_Type) {
-                if (ints_are_bounded && Py_ABS(Py_SIZE(key)) > 1)
+            if (keys_are_all_same_type) {
+                if (key_type == &PyLong_Type &&
+                    ints_are_bounded &&
+                    Py_ABS(Py_SIZE(key)) > 1) {
+
                     ints_are_bounded = 0;
+                }
+                else if (key_type == &PyUnicode_Type &&
+                         strings_are_latin &&
+                         PyUnicode_KIND(key) != PyUnicode_1BYTE_KIND) {
+
+                        strings_are_latin = 0;
+                    }
+                }
             }
-            else if (key_type == &PyUnicode_Type){
-                if (strings_are_latin &&
-                    PyUnicode_KIND(key) != PyUnicode_1BYTE_KIND)
-                strings_are_latin = 0;
-            }
-        }
 
         /* Choose the best compare, given what we now know about the keys. */
         if (keys_are_all_same_type) {
@@ -2290,10 +2299,12 @@
         if (keys_are_in_tuples) {
             /* Make sure we're not dealing with tuples of tuples
              * (remember: here, key_type refers list [key[0] for key in keys]) */
-            if (key_type == &PyTuple_Type)
+            if (key_type == &PyTuple_Type) {
                 ms.tuple_elem_compare = safe_object_compare;
-            else
+            }
+            else {
                 ms.tuple_elem_compare = ms.key_compare;
+            }
 
             ms.key_compare = unsafe_tuple_compare;
         }