Find all unsorted pairs in partially sorted array

It depends a little bit on what you mean exactly by "partially sorted" - One could argue that every array is partially sorted to some degree.\nSince this algorithm has worst-case complexity O(n^2) anyway (consider the input sorted in descending order), you might as well go down the straight-forward route:\nret = []\n\nfor i in range(len(array)):\n for j in range(i, len(array)):\n if array[i] > array[j]:\n ret.append((array[i], array[j]))\n\nreturn ret\n\nThis works very well for random arrays.\nHowever, I suppose what you have in mind is more something that there are larger stretches inside the array where the numbers are sorted but that that's not the case for the array as a whole.\nIn that case, you can save a bit of time over the naive approach above by first identifying those stretches - this can be done in a linear pass. Once you have them, you only have to compare these stretches with each other, and you can use binary search for that (since the stretches are in sort order).\nHere's a Python implementation of what I have in mind:\n# find all sorted stretches\nstretches = []\nbegin = 0\nfor i in range(1, len(array)):\n if array[i-1] > array[i]:\n stretches.append(array[begin:i])\n begin = i\nif i+1 > begin:\n stretches.append(array[begin:])\n\n# compare stretches\nret = []\nfor i in range(len(stretches)):\n stretchi = stretches[i]\n stretchi_rev = None\n \n for j in range(i+1, len(stretches)):\n stretchj = stretches[j]\n\n if stretchi[-1] > stretchj[0]:\n if stretchi_rev is None:\n stretchi_rev = list(reversed(stretchi))\n\n hi = len(stretchj)\n for x in stretchi_rev:\n i = bisect.bisect_left(stretchj, x, 0, hi)\n if i == 0:\n break\n else:\n for y in stretchj[:i]:\n ret.append((x, y))\n hi = i\n \nreturn ret\n\nFor random arrays, this will be slower than the first approach. But if the array is big, and the amount of partially sorted portions is high enough, this algorithm will at some point starting to beat the brute-force search.",