Cycle Sort in Java — An In-Depth Guide

When preparing for interviews at top companies like Amazon, Google, and Microsoft, you will often encounter problems that require efficient in-place sorting. One such elegant yet lesser-known algorithm is Cycle Sort. Unlike traditional sorting algorithms, Cycle Sort minimizes the number of writes, making it highly efficient when write operations are costly.

---

🔹 What is Cycle Sort?

Cycle Sort is an in-place, comparison-based sorting algorithm. It works by placing each element directly in its correct position using the concept of cycles. Once an element is placed in the right spot, we continue the cycle until the entire array is sorted.

Key Features:

• Minimizes the number of write operations (best choice when memory writes are expensive).
• Performs sorting in-place with constant space complexity (O(1)).
• Has a time complexity of O(n²), which makes it less practical for large datasets.

---

🔹 How Cycle Sort Works

Let’s break the algorithm into simple steps:

1. Start with the first element (cycle start).
2. Count how many elements are smaller than it → this gives its correct position.
3. If it’s not in the correct position, swap it with the element at that position.
4. Repeat the cycle until the element reaches its correct place.
5. Continue with the next element and repeat.

Example: Sort the array [3, 1, 4, 2]

Step 1: Start with 3
Elements smaller than 3 → (1, 2) → position = 2
Swap 3 with element at index 2

Array becomes: [4, 1, 3, 2]

Step 2: Place 4
Elements smaller than 4 → (1, 3, 2) → position = 3
Swap 4 with element at index 3

Array becomes: [2, 1, 3, 4]

Step 3: Place 2
Elements smaller than 2 → (1) → position = 1
Swap 2 with element at index 1

Array becomes: [1, 2, 3, 4]

✅ Sorted Array

Diagram:

Original:  [3] [1] [4] [2]

Cycle 1:   [4] [1] [3] [2]
Cycle 2:   [2] [1] [3] [4]
Cycle 3:   [1] [2] [3] [4] → Sorted

---

🔹 Java Implementation

import java.util.*;

public class CycleSort {
    public static void cycleSort(int[] arr) {
        int writes = 0;
        int n = arr.length;

        for (int cycleStart = 0; cycleStart < n - 1; cycleStart++) {
            int item = arr[cycleStart];
            int pos = cycleStart;

            // Find the correct position for the item
            for (int i = cycleStart + 1; i < n; i++) {
                if (arr[i] < item) pos++;
            }

            // If item is already in the correct place
            if (pos == cycleStart) continue;

            // Skip duplicates
            while (item == arr[pos]) pos++;

            // Swap item into correct position
            int temp = arr[pos];
            arr[pos] = item;
            item = temp;
            writes++;

            // Rotate the rest of the cycle
            while (pos != cycleStart) {
                pos = cycleStart;
                for (int i = cycleStart + 1; i < n; i++) {
                    if (arr[i] < item) pos++;
                }
                while (item == arr[pos]) pos++;

                temp = arr[pos];
                arr[pos] = item;
                item = temp;
                writes++;
            }
        }

        System.out.println("Total Writes: " + writes);
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 2};
        cycleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

---

🔹 Complexity Analysis

• Time Complexity: O(n²) in all cases (due to nested loops).
• Space Complexity: O(1) (in-place sorting).
• Best Feature: Minimizes number of writes, hence useful for systems with limited write cycles (e.g., EEPROMs, flash memory).

---

🔹 When to Use Cycle Sort?

Cycle Sort is rarely used in production due to O(n²) time complexity. However, it’s extremely valuable for:

• Interview Problems: Used in LeetCode problems like "Missing Number", "Find All Duplicates", and "First Missing Positive".
• Special Systems: Ideal where write operations are costly or limited.
• Educational Purpose: Helps understand in-place sorting and cycle decomposition.

---

🔹 Comparison with Other Sorting Algorithms

Algorithm	Time Complexity	Space Complexity	Best For
Cycle Sort	O(n²)	O(1)	Minimal writes, interview problems
Quick Sort	O(n log n) avg	O(log n)	General purpose efficient sorting
Insertion Sort	O(n²)	O(1)	Small / nearly sorted arrays

---

✅ Conclusion

Cycle Sort may not be the fastest sorting algorithm, but it’s a powerful tool in interview preparation and in cases where minimizing writes is critical. By directly placing each element into its correct position, it introduces the concept of cycle decomposition, which is highly valued in coding interviews at big tech companies. While you may not use it every day, mastering Cycle Sort will definitely give you an edge in problem-solving.