Skip to main content

Cycle Sort

  • does minimum memory writes
  • Not stable sorting
  • In place
  • Worst case:
    • Time: θ(n2)θ(n ^ 2), Space: O(1)O(1)
  • Helps to solve ques like min swap to sort the array
# works for distinct elements
def cycleSortDistinct(arr):
    N = len(arr)
    for cs in range(N - 1):
        pos, item = cs, arr[cs]
        for i in range(cs + 1, N):
            if arr[i] < item:
                pos += 1
        if pos == cs:
            continue
        arr[pos], item = item, arr[pos]
        while pos != cs:
            pos = cs
            for i in range(cs + 1, N):
                if arr[i] < item:
                    pos += 1
            if pos == cs:
                continue
            arr[pos], item = item, arr[pos]

Left operations​

  • The above will not work for list of objects
  • Stable
def countingSort(arr, k):
    output = [0] * len(arr)
    count = [0] * k
    for n in arr:
        count[n] += 1
    for i in range(1, k):
        count[i] += count[i - 1]
    for x in reversed(arr):
        output[count[x] - 1] = x
        count[x] -= 1
    for i in range(len(arr)):
        arr[i] = output[i]