Here's a pretty common pattern for sorting algorithms:

def sort(l):
 while not is_sorted(l):
 choose indices i, j
 assert i < j
 if l[i] > l[j]:
 l[i], l[j] = l[j], l[i]

These algorithms work well because the indices i and j are chosen carefully, based on the state of the list l.

However, what if we couldn't see l, and just had to choose blindly? How fast could we sort the list then?

Your challenge is to write a function that outputs a random pair of indices, given only the length of l. Specifically, you must output two indices, i, j, with 0 <= i < j < len(l). Your function should work on any length of list, but it will be scored on a list of length 100.

Your score is the mean number of index choices necessary to sort a uniformly randomly shuffled list according to the above pattern, where the indices are chosen according to your function.

I will score submissions, taking the mean number of index choices over 1000 trials on a uniformly randomly shuffled list of length 100 with no repeated entries.

I reserve the right to run less trials if the submission is clearly non-competitive or does not terminate, and I will run more trials to differentiate the top competitors to find a single winner. If multiple top submissions remain within the margin of error at the limit of my computational resources, I will declare the earlier submission the winner, until further computational resources can be brought to bear.

Here's an example scoring program, in Python:

import random
def score(length, index_chooser):
 steps = 0
 l = list(range(length))
 random.shuffle(l)
 while True:
 for x in range(length-1):
 if l[x] > l[x+1]:
 break
 else:
 return steps
 i, j = index_chooser(length)
 assert(i < j)
 if l[i] > l[j]:
 l[i], l[j] = l[j], l[i]
 steps += 1

Your function may not maintain any mutable state, interact with global variables, affect the list l, etc. Your function's only input must be the length of the list l, and it must output a ordered pair of integers in the range [0, len(l)-1] (or appropriate for your language's list indexing). Feel free to ask whether something's allowed in the comments.

Submissions may be in any free-to-use language. Please include a scoring harness if one has not already been posted for your language. You may post a provisional score, but I will leave a comment with the official score.

Scoring is the mean number of steps to a sorted list on a uniformly randomly shuffled list of length 100. Good luck.

Python, score ≈ 10990

def bubble(length):
 i = random.randrange(length - 1)
 return i, i + 1

Apparently a randomized bubble sort doesn’t do all that much worse than a normal bubble sort.

Score ~4620

def rand_step(n):
	step_size = random.choice([1, 1, 4, 16])
	
	if step_size > n - 1:
		step_size = 1 
	
	start = random.randint(0, n - step_size - 1)
	return (start, start + step_size)

Try it online!

Outputs random indices whose distance apart is chosen uniformly from [1,1,4,16]. The idea is to have a mix of 1-step swaps with swaps at larger scales.

I hand-tweaked these values for lists of length 100, and they are likely far from optimal. Some machine search could probably optimize the distribution over distances for the random-pair-with-chosen-distance strategy.

Score: ~28500?

def x_and_y(l):
 x = random.choice(range(l))
 y = random.choice(range(l))
 while y == x and l != 1: y = random.choice(range(l))
 return sorted([x,y])

Try it online!

This solution just selects distinct values for x and y randomly from the range and returns them in sorted order. As far as I can tell, this performs better than choosing x then choosing y from the remaining values.