Cycle sort works as follows:

• Go through the elements of the list.
• For each element:
  • Count how many items on the list are smaller than the element; this gives the index of the element.
  • If the element is already located at the correct index, do nothing.
  • Else: move the element to its correct place, taking the element that is at that place and process that element next.

Implement cycle sort. Also determine its time complexity in big-O notation. Can you imagine any advantage of cycle sort?

Note: Cycle sort has two things that you have to be aware of:

• It is best to make sure that you use an in-place implementation, so that you will always make the correct counts. This means that you best not use a separate variable to store the element that you are processing, but always swap the value that you found at the location where the element is supposed to be with the element that you are currently processing.
• If the list contains double elements, you can get into an endless loop, as you may constantly be trying to switch an element with itself. To solve this, you have two options:
  • You insert the element not at the position that is indicated, but if you see that there is already an element with that value there, you insert it after the sequence of all the elements with that same value. However, you should take into account that if during the process of moving up in the list, you get to the index that you are currently moving an element from, that the element is already at its correct position.
  • You simply choose to implement this algorithm for lists with only unique values. This simplifies the development of the algorithm quite a bit. I my answer I will show both implementations.

Note: The submission of this exercise is in markdown and therefore won’t be tested. Use your preferred code editor or Papyrus¹ to test your code.