{"id":1021,"date":"2026-11-17T13:46:00","date_gmt":"2026-11-17T12:46:00","guid":{"rendered":"https:\/\/grindloop.ai\/blog\/?p=1021"},"modified":"2026-11-16T18:20:31","modified_gmt":"2026-11-16T17:20:31","slug":"comparison-method-violates-general-contract","status":"publish","type":"post","link":"https:\/\/grindloop.ai\/blog\/comparison-method-violates-general-contract\/","title":{"rendered":"Comparison Method Violates Its General Contract in Kotlin sortedWith: Why Only Big Lists Crash"},"content":{"rendered":"<p>A store list sorts fine in every test. Then production logs show <code>IllegalArgumentException: Comparison method violates its general contract!<\/code> from <code>sortedWith<\/code>. The message means your comparator breaks a rule that the sort relies on. In the code below, two stacked causes produce it. First, the comparator answers -1 in both directions when both stores are pinned. It also never returns 0 for two stores at the same distance. Second, the JVM&#8217;s TimSort only notices this while it merges sorted runs. A list under 32 elements never merges, so small test lists sort quietly and never throw. In our repro, 10-item lists never crashed. With 200 items, 203 of 1,000 random lists crashed. The fix is to build the comparator from <code>compareByDescending<\/code> and <code>thenBy<\/code>. They produce the signs for you. Then test it with a list of at least 32 elements that includes ties.<\/p>\n\n<h2>A pinned-first store list that crashes only in production<\/h2>\n\n<p>The running example is a store picker. Pinned stores go first. Everything else is ordered by distance from the user. Distances come back rounded to 0.5 km, so ties are common. Here is the comparator.<\/p>\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"kotlin\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">data class Store(val id: Int, val pinned: Boolean, val distanceKm: Double)\n\nval byPinnedThenDistance = Comparator&lt;Store&gt; { a, b -&gt;\n    when {\n        a.pinned -&gt; -1\n        b.pinned -&gt; 1\n        else -&gt; if (a.distanceKm &lt; b.distanceKm) -1 else 1\n    }\n}\n\nfun sortStores(stores: List&lt;Store&gt;) = stores.sortedWith(byPinnedThenDistance)<\/pre>\n\n\n<p>We generated random lists with a fixed seed. One store in ten is pinned. Distances are multiples of 0.5 km from 0 to 9.5. Each list size ran 1,000 times on Kotlin 2.4.20 and OpenJDK 25.<\/p>\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">size=10  crashes=0\/1000\nsize=31  crashes=0\/1000\nsize=32  crashes=6\/1000\nsize=50  crashes=4\/1000\nsize=200 crashes=203\/1000\n\njava.lang.IllegalArgumentException: Comparison method violates its general contract!\n    at java.util.TimSort.mergeLo\n    at java.util.TimSort.mergeAt\n    at java.util.TimSort.mergeCollapse\n    at java.util.TimSort.sort\n    at java.util.Arrays.sort\n    at kotlin.collections.ArraysKt___ArraysJvmKt.sortWith(_ArraysJvm.kt:2206)\n    at kotlin.collections.CollectionsKt___CollectionsKt.sortedWith(_Collections.kt:1260)<\/pre>\n\n\n<p>The size cliff is sharp. No list under 32 crashed. At 32 a few did. At 200 roughly one list in five did. A unit test with eight hand-picked stores passes every time. A user with 200 nearby stores sees a crash on some loads. Other loads work.<\/p>\n\n<p>The trace also shows where the work happens. In the <a href=\"https:\/\/github.com\/JetBrains\/kotlin\/blob\/v2.4.20\/libraries\/stdlib\/common\/src\/generated\/_Collections.kt\" target=\"_blank\" rel=\"noopener\">Kotlin 2.4.20 stdlib<\/a>, <code>sortedWith<\/code> copies the list to an array. On the JVM, <a href=\"https:\/\/github.com\/JetBrains\/kotlin\/blob\/v2.4.20\/libraries\/stdlib\/jvm\/src\/generated\/_ArraysJvm.kt\" target=\"_blank\" rel=\"noopener\"><code>sortWith<\/code><\/a> then calls <code>java.util.Arrays.sort<\/code>. So the exception comes from the JDK sort, not from Kotlin.<\/p>\n\n<h2>Comparison method violates its general contract when one pair gets two answers<\/h2>\n\n<p>The <a href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/21\/docs\/api\/java.base\/java\/util\/Comparator.html\" target=\"_blank\" rel=\"noopener\"><code>Comparator<\/code> contract<\/a> has three rules. Swapping the arguments must flip the sign. Ordering must be transitive. Two elements that compare equal must compare the same way against every third element. This is root cause one. Our comparator breaks the first rule in two places.<\/p>\n\n<p>The pinned branch is the first. Take two pinned stores, <code>a<\/code> and <code>b<\/code>. <code>compare(a, b)<\/code> hits <code>a.pinned<\/code> and returns -1. <code>compare(b, a)<\/code> hits <code>b.pinned<\/code> first and also returns -1. Each store claims to come before the other. The <code>when<\/code> reads naturally from top to bottom. That hides the missing case where both flags are true.<\/p>\n\n<p>The distance branch is the second. It has no path that returns 0. Two unpinned stores at 2.0 km return 1 in both directions. Even <code>compare(c, c)<\/code> on the same store returns 1. So every tie is a contradiction. With distances rounded to 0.5 km, a 200-store list has many ties.<\/p>\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">two pinned stores:   compare(a, b) = -1   compare(b, a) = -1\nsame store:          compare(c, c) = 1\ndistance NaN vs 2.0: compare(n, c) = 1    compare(c, n) = 1<\/pre>\n\n\n<p>The last line shows a third trap in the same branch. A store with an unknown location often gets <code>Double.NaN<\/code> as its distance. Every <code>&lt;<\/code> comparison with NaN is false. So the hand-written branch returns 1 both ways for that store too.<\/p>\n\n<h2>TimSort only checks the contract while it merges<\/h2>\n\n<p>Root cause two is in the sort itself. The JDK&#8217;s <a href=\"https:\/\/github.com\/openjdk\/jdk\/blob\/master\/src\/java.base\/share\/classes\/java\/util\/TimSort.java\" target=\"_blank\" rel=\"noopener\"><code>TimSort<\/code><\/a> sets <code>MIN_MERGE<\/code> to 32. For a range smaller than that, it runs a binary insertion sort with no merges. The exception is thrown in only two places, <code>mergeLo<\/code> and <code>mergeHi<\/code>. Each fires when a merge runs out of elements in a way that a valid comparator can&#8217;t cause. A list of 31 stores never reaches either method. The broken comparator still runs. It just produces some order and returns.<\/p>\n\n<p>Above 32 elements, detection still isn&#8217;t guaranteed. A merge throws only when the contradictions happen to empty one side early. That is why 200-store lists crashed about 20% of the time instead of always. The <a href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/21\/docs\/api\/java.base\/java\/util\/Arrays.html#sort(T%5B%5D,java.util.Comparator)\" target=\"_blank\" rel=\"noopener\"><code>Arrays.sort<\/code> docs<\/a> say this outright. The <code>IllegalArgumentException<\/code> is marked optional, thrown &#8220;if the comparator is found to violate&#8221; the contract.<\/p>\n\n<p>Android behaves the same way. Its <a href=\"https:\/\/android.googlesource.com\/platform\/libcore\/+\/refs\/heads\/main\/ojluni\/src\/main\/java\/java\/util\/TimSort.java\" target=\"_blank\" rel=\"noopener\">libcore <code>TimSort<\/code><\/a> comes from OpenJDK. It has the same 32-element threshold and the same message in <code>mergeLo<\/code> and <code>mergeHi<\/code>. So on current Android, the crash also depends on list size and data.<\/p>\n\n<h2>The fix: let compareBy build the signs<\/h2>\n\n<p>Describe the ordering as keys and let the stdlib produce the signs. More branches in the <code>when<\/code> would leave the same risk in place.<\/p>\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"kotlin\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">val byPinnedThenDistance = compareByDescending&lt;Store&gt; { it.pinned }\n    .thenBy { it.distanceKm }\n    .thenBy { it.id }\n\nfun sortStores(stores: List&lt;Store&gt;) = stores.sortedWith(byPinnedThenDistance)<\/pre>\n\n\n<p><code>compareByDescending { it.pinned }<\/code> uses <code>Boolean.compareTo<\/code>, so <code>true<\/code> sorts first. Two pinned stores now compare equal on that key. <a href=\"https:\/\/kotlinlang.org\/api\/core\/kotlin-stdlib\/kotlin.comparisons\/then-by.html\" target=\"_blank\" rel=\"noopener\"><code>thenBy<\/code><\/a> only runs when the earlier keys are equal. So pinned stores fall through to distance as well.<\/p>\n\n<p><code>thenBy { it.distanceKm }<\/code> compares boxed doubles with <code>compareTo<\/code>. The <a href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/21\/docs\/api\/java.base\/java\/lang\/Double.html\" target=\"_blank\" rel=\"noopener\"><code>Double<\/code> docs<\/a> define that as a total order. NaN equals itself and sorts above positive infinity. So stores with an unknown distance land at the end, consistently.<\/p>\n\n<p><code>thenBy { it.id }<\/code> isn&#8217;t needed for the contract. Ties already return 0. It makes the order deterministic when the input order changes. <a href=\"https:\/\/kotlinlang.org\/api\/core\/kotlin-stdlib\/kotlin.collections\/sorted-with.html\" target=\"_blank\" rel=\"noopener\"><code>sortedWith<\/code> is stable<\/a>, so without it, tied stores keep their input order. A server that returns stores in a different order each time would reshuffle the list.<\/p>\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">fixed size=10  crashes=0 wrongOrder=0\nfixed size=200 crashes=0 wrongOrder=0\nfixed, input [NaN (id 4), 2.0 km (id 3), pinned 1.0 km (id 2)] -&gt; ids [2, 3, 4]<\/pre>\n\n\n<p>Zero crashes across the same 1,000 seeds at both sizes. Every result has pinned stores first and distances ascending. The test that guards this needs at least 32 stores, including two pinned and several ties. Otherwise it exercises the binary insertion path only and proves nothing about the merge.<\/p>\n\n<h2>How to answer it in a technical round<\/h2>\n\n<p>An interviewer may hand you the stack trace and the comparator. Work from the message back to the code.<\/p>\n\n<ol>\n<li>Name the message. It comes from TimSort and means the comparator broke its contract. The list isn&#8217;t being changed by another thread.<\/li>\n<li>Test antisymmetry by hand. Call <code>compare(a, b)<\/code> and <code>compare(b, a)<\/code> for two pinned stores. Both return -1.<\/li>\n<li>Test ties and identity. <code>compare(c, c)<\/code> returns 1, so the distance branch never says equal. Mention NaN as the same problem.<\/li>\n<li>Explain why tests passed. TimSort runs no merges below 32 elements. Only merges throw. Above that, detection depends on the data.<\/li>\n<li>Fix it with <code>compareByDescending { it.pinned }.thenBy { it.distanceKm }<\/code>. Add a tie-breaker if the order must be stable across loads.<\/li>\n<li>Say which test you&#8217;d add. Use 32 or more stores with ties, two pinned stores and a NaN distance.<\/li>\n<\/ol>\n\n<p>Step 4 explains why the bug reached production. The debugging round also scores the search past the first fix. Hass covers that in <a href=\"https:\/\/grindloop.ai\/blog\/android-debugging-interview-second-bug\/\">finding the bug and still not passing<\/a>. Our <a href=\"https:\/\/grindloop.ai\/blog\/kotlin-hashset-contains-returns-false\/\">HashSet contains() post<\/a> covers a related contract, where <code>hashCode<\/code> broke after the object changed.<\/p>\n\n<h2>Wrong answers that keep the crash or hide it<\/h2>\n\n<p>&#8220;Return 0 when the distances are equal.&#8221; That fixes the tie branch and leaves the pinned branch alone. We ran that half fix on the same 1,000 seeds. Lists of 200 still crashed 11 times. The crash got rarer. That makes it harder to catch.<\/p>\n\n<p>&#8220;Something is modifying the list while it sorts.&#8221; <code>sortedWith<\/code> sorts a private array copy, as the stdlib source shows. Nothing else can touch it. The message is about the comparator&#8217;s answers.<\/p>\n\n<p>&#8220;Wrap the sort in try\/catch and fall back to the unsorted list.&#8221; The crash goes away. Users who hit it now get the unsorted list, with pinned stores buried. The comparator stays broken. No one sees an error to fix.<\/p>\n\n<p>&#8220;Subtract the values instead: <code>(a.distanceKm - b.distanceKm).toInt()<\/code>.&#8221; Truncation turns a 0.5 km gap into 0. In our run, 1.0 equaled 1.5 and 1.5 equaled 2.0. Yet 1.0 came before 2.0. That breaks the third rule of the contract. With <code>Int<\/code> fields, subtraction can also overflow. <code>Int.MIN_VALUE - 1<\/code> came out positive.<\/p>","protected":false},"excerpt":{"rendered":"<p>Comparison method violates its general contract means your comparator answers both ways. TimSort only checks lists of 32+, so tests pass. Repro and fix.<\/p>\n","protected":false},"author":2,"featured_media":1022,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"rank_math_title":"Comparison Method Violates Its General Contract in Kotlin sortedWith","rank_math_description":"Comparison method violates its general contract means your comparator answers both ways. TimSort only checks lists of 32+, so tests pass. Repro and fix.","rank_math_focus_keyword":"comparison method violates its general contract","footnotes":""},"categories":[9,7],"tags":[15,16,91,12,45],"class_list":["post-1021","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-bug-squash","category-java","tag-android","tag-interview-prep","tag-java-collections","tag-kotlin","tag-technical-interview"],"_links":{"self":[{"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/posts\/1021","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/comments?post=1021"}],"version-history":[{"count":1,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/posts\/1021\/revisions"}],"predecessor-version":[{"id":1023,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/posts\/1021\/revisions\/1023"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/media\/1022"}],"wp:attachment":[{"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/media?parent=1021"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/categories?post=1021"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/grindloop.ai\/blog\/wp-json\/wp\/v2\/tags?post=1021"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}