Instructions to run the algorithms

Odd Even Transposition Sorting algorithm

• Compile the java code: javac OddEvenTranspositionSort.java
• Run the java file: java OddEvenTranspositionSort

Atsushi Sasaki's Sorting algorithm

• Compile the java code: javac Sasaki.java
• Run the java file: java Sasaki

Alternative Time Optimal Sorting Algorithm

• Compile the java code: javac AlternateTimeOptimalSorting.java
• Run the java file: java AlternateTimeOptimalSorting

Algorithmic Complexities and Number of Steps Required

Algorithm	Time Complexity (Worst)	Space Complexity	Number of Steps (Rounds)
Odd-Even Transposition Sort	O(n²)	O(n)	n
Atsushi Sasaki's Time-Optimal	O(n * (n-1))	O(n)	n - 1
Alternate Time-Optimal Sorting	O(n/3 * (n-1))	O(n)	n - 1

---

Runtime in milliseconds for different number of processing entites

Input Type	Odd-Even Transposition	Atsushi Sasaki's Sort	Alternate Time-Optimal
10 entites	16 ms	31 ms	9 ms
20 entites	26 ms	21 ms	16 ms
30 entites	27 ms	29 ms	18 ms
50 entites	33 ms	34 ms	17 ms

Data Structure Used, Time Complexity and Space Complexity for the codes.

1. Odd-Even Transposition Sort

• Data Structure Used: - int[] array — used to hold and manipulate the elements being sorted directly in memory.
• Time Complexity: O(n²) - The algorithm performs n phases, and in each phase, up to n/2 comparisons/swaps may happen — resulting in a worst-case of O(n²).
• Space Complexity: O(n) - Uses the input array and a list of threads (up to n/2 per phase), so space usage remains linear.

---

2. Atsushi Sasaki’s Time-Optimal Sort

• Data Structure Used: Linked list of nodes (Node), each containing two elements (Element), with threading to parallelize comparisons and swaps.
• Time Complexity: O(n^2) due to n-1 rounds with O(n) work per round.
• Space Complexity: O(n) for storing elements and nodes, plus space for threads.

---

3. Alternate Time-Optimal Sort

• Data Structure Used: int[]- array — used for in-place sorting and accessing neighbors for compare-and-swap operations.
• Time Complexity: O(n²) - The algorithm runs for n - 1 rounds, and in each round, up to n/3 comparisons happen — leading to a worst-case behavior proportional to n².
• Space Complexity: O(n) - Only the input array and a thread array of size n are used; no additional data structures grow beyond linear space.

---