I learned about this from Matt Parker’s Stand-Up Maths channel. It was originally conceived as a counterexample, a sorting algorithm that was obviously broken, but it does actually sort correctly. The algorithm:

for i = 1 to n do  
	for j = 1 to n do  
		if A[i] < A[j] then  
			swap A[i] and A[j]

It has a few quirks (like j accessing elements outside of i’s range, and the A[i] < A[j] comparator being backward) that should break it, but they all work together to make the algorithm correctly (if inefficiently) sort the input.

paper describing the algorithm in more detail.

  • pelya@lemmy.world
    3·
    8 days ago

    I would expect something worse than bubble sort. No idea whether it will even work:

    void reverse(auto A, int start, int end) {
  for (int i = 0; i < (end - start) / 2; i = i + 1) {
    auto tmp = A[start + i];
    A[start + i] = A[end - i];
    A[end - i] = tmp;
  }
}

for (int j = 0; j < N; j = j + 1) {
  for (int i = 0; i < N; i = i + 1) {
    if (A[i] < A[i + 1]) {
      reverse(A, i, N);
    }
  }
}