# ICan’tBelieveItCanSort

5 min read

## The simplest sort possible

Read section The simplest sort possibleHalf 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,
]);
```

```
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(n^{2}) 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 descendingAnother 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,
]);
```

```
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)## Optimized version

Read section Optimized versionThe 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,
]);
```

```
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 descendingLike 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,
]);
```

```
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,
]);
```