• Archive
    • Computer Science

    ICan’tBelieveItCanSort

    5 min read

    The simplest sort possible

    Read section The simplest sort possible

    Half a year ago, a short paper was published by Stanley P. Y. Fung describing the simplest sorting algorithm imaginable - just a simple double loop involving a comparison and a swap. See for yourself:

    function ICantBelieveItCanSort(A) {
  for (let i = 0; i < A.length; i += 1) {
    for (let j = 0; j < A.length; j += 1) {
      if (A[i] < A[j]) {
        [A[i], A[j]] = [A[j], A[i]];
      }
    }
  }
  return A;
}
ICantBelieveItCanSort([
  489, 945, 206, 889, 841, 564, 591, 150, 581, 898, 295, 701, 212, 667, 197, 634, 919, 666, 160, 117, 401, 494, 277, 62,
  853, 222, 405, 688, 552, 375, 172, 342, 122, 814, 360, 907, 678, 599, 994, 647, 449, 417, 471, 301, 185, 735, 214,
  535, 845, 180,
]);

    The algorithm is so primitive that one does not even need to memorize its big-O. In both its best-case and worst-case, it performs O(n2) comparisons and swaps. No additional memory is allocated (besides tmp which will be optimized to use a register), thus its space complexity is O(1).

    Sorting descending

    Read section Sorting descending

    Another interesting property is that the sort order can be reversed (made descending) not just by modifying the comparator, but also by swapping the order of the loops:

    function ICantBelieveItCanSortDesc(A) {
  for (let j = 0; j < A.length; j += 1) {
    for (let i = 0; i < A.length; i += 1) {
      if (A[i] < A[j]) {
        [A[i], A[j]] = [A[j], A[i]];
      }
    }
  }
  return A;
}
ICantBelieveItCanSortDesc([
  489, 945, 206, 889, 841, 564, 591, 150, 581, 898, 295, 701, 212, 667, 197, 634, 919, 666, 160, 117, 401, 494, 277, 62,
  853, 222, 405, 688, 552, 375, 172, 342, 122, 814, 360, 907, 678, 599, 994, 647, 449, 417, 471, 301, 185, 735, 214,
  535, 845, 180,
]);

    Visual demonstration (video)

    Read section Visual demonstration (video)
    https://www.youtube.com/watch?v=bydMm4cJDeU

    This video is hosted by YouTube. By loading this video, you agree with Google's Privacy Policy.

    Optimized version

    Read section Optimized version

    The paper also offers a slightly optimized version by identifying unnecessary iterations. The primary improvement is that the inner loop j initially does much less work.

    function OptimizedICantBelieveItCanSort(A) {
  for (let i = 1; i < A.length; i += 1) {
    for (let j = 0; j < i; j += 1) {
      if (A[i] < A[j]) {
        [A[i], A[j]] = [A[j], A[i]];
      }
    }
  }
  return A;
}
OptimizedICantBelieveItCanSort([
  489, 945, 206, 889, 841, 564, 591, 150, 581, 898, 295, 701, 212, 667, 197, 634, 919, 666, 160, 117, 401, 494, 277, 62,
  853, 222, 405, 688, 552, 375, 172, 342, 122, 814, 360, 907, 678, 599, 994, 647, 449, 417, 471, 301, 185, 735, 214,
  535, 845, 180,
]);

    Sorting descending

    Read section Sorting descending

    Like the original, the loops can be reordered to invert the sorting order without having to swap the comparator, as long as the loop condition is updated accordingly.

    function OptimizedICantBelieveItCanSortDesc(A) {
  for (let j = 1; j < A.length; j += 1) {
    for (let i = 0; i < j; i += 1) {
      if (A[i] < A[j]) {
        [A[i], A[j]] = [A[j], A[i]];
      }
    }
  }
  return A;
}
OptimizedICantBelieveItCanSortDesc([
  489, 945, 206, 889, 841, 564, 591, 150, 581, 898, 295, 701, 212, 667, 197, 634, 919, 666, 160, 117, 401, 494, 277, 62,
  853, 222, 405, 688, 552, 375, 172, 342, 122, 814, 360, 907, 678, 599, 994, 647, 449, 417, 471, 301, 185, 735, 214,
  535, 845, 180,
]);

    Tags