1. It's accidentally quadratic
midpoint = (first + last)
midpoint = (first + last) // 2
The consequence of this mistake is that
binarySearch takes \$Θ(n)\$ to find the location, instead of the intended \$O(\log n)\$. And
binarySearch is called for every item in the list, making the overall runtime \$Θ(n^2)\$ instead of the intended \$O(n \log n)\$.
2. Review of
There's no docstring. What does it do? What arguments do I pass? What does it return?
The Python style guide (PEP8) recommends:
4 spaces per indentation level
Always surround these binary operators with a single space on either side: [...] comparisons (
Following PEP8 will make it easier for you to collaborate with other Python programmers.
A local variable
found is used to exit the
while loop. But Python's
break statement also exits a loop, and if you used this you'd avoid the need for the variable.
else: if can be written
elif:, saving a level of indentation.
Consider using the built-in
3. Alternative approach
The rearrangement of items that happens when you sort a list is known as a permutation. For example, let's take this list of items:
When we sort the list, each item moves to a new position in the list, shown by the arrows:
We can draw the same arrows on a single row of items, showing where each item goes in the permutation:
The structure of the permutation becomes clear if we rearrange the items so that none of the arrows are crossing. Every permutation consists of one or more cycles: in this case there is a 1-cycle sending 6 to itself, a 2-cycle swapping 3 and 5, and a 7-cycle sending 4 to 9 to 2 to 1 to 8 to 7 to 0 to 4.
It takes \$n-1\$ swaps to implement a cycle of length \$n\$. So if the sorted permutation of a list can be decomposed into cycles with lengths \$a, b, c, \ldots, z\$ then the minimum number of swaps needed to sort the list is \$(a - 1) + (b - 1) + (c - 1) + \cdots + (z - 1)\$.
Here's an implementation that finds the cycles first and then uses their lengths to count the swaps. (It's not actually necessary to find the cycles, you could just count the swaps as you go along, but I think this is clearer to begin with.)
"""Generate cycles in the cyclic decomposition of a permutation.
>>> list(cycle_decomposition([7, 2, 9, 5, 0, 3, 6, 8, 1, 4]))
[[0, 7, 8, 1, 2, 9, 4], [3, 5], ]
unvisited = set(permutation)
j = i = unvisited.pop()
cycle = [i]
j = permutation[j]
if j == i:
"""Return minimum swaps needed to sort the sequence.
>>> minimum_swaps([2, 1])
>>> minimum_swaps([4, 8, 1, 5, 9, 3, 6, 0, 7, 2])
permutation = sorted(range(len(seq)), key=seq.__getitem__)
return sum(len(cycle) - 1 for cycle in cycle_decomposition(permutation))