Repository: TheAlgorithms/Java
Pull request #3205 (2022-08-03 17:48:14)

Create a new Strand Sort Algorithm
### **Describe your change:**

- [X] Add an algorithm?

#### References

[Strand sort algorithm](https://en.wikipedia.org/wiki/Strand_sort)

### **Checklist:**

<!-- Remove items that do not apply. For completed items, change [ ] to [x]. -->

- [X] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [X] I know that pull requests will not be merged if they fail the automated tests.
- [X] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [X] All new Java files are placed inside an existing directory.
- [X] All filenames are in all uppercase characters with no spaces or dashes.
- [X] All functions and variable names follow Java naming conventions.
- [X] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.



Patch:
diff --git a/src/main/java/com/thealgorithms/sorts/StrandSort.java b/src/main/java/com/thealgorithms/sorts/StrandSort.java
new file mode 100644
index 00000000..8b31f7c4
--- /dev/null
+++ b/src/main/java/com/thealgorithms/sorts/StrandSort.java
@@ -0,0 +1,42 @@
+package com.thealgorithms.sorts;
+import java.util.Iterator;
+import java.util.LinkedList;
+ 
+public class StrandSort{
+	// note: the input list is destroyed
+	public static <E extends Comparable<? super E>> 
+	LinkedList<E> strandSort(LinkedList<E> list){
+		if(list.size() <= 1) return list;
+ 
+		LinkedList<E> result = new LinkedList<E>();
+		while(list.size() > 0){
+			LinkedList<E> sorted = new LinkedList<E>();
+			sorted.add(list.removeFirst()); //same as remove() or remove(0)
+			for(Iterator<E> it = list.iterator(); it.hasNext(); ){
+				E elem = it.next();
+				if(sorted.peekLast().compareTo(elem) <= 0){
+					sorted.addLast(elem); //same as add(elem) or add(0, elem)
+					it.remove();
+				}
+			}
+			result = merge(sorted, result);
+		}
+		return result;
+	}
+ 
+	private static <E extends Comparable<? super E>>
+	LinkedList<E> merge(LinkedList<E> left, LinkedList<E> right){
+		LinkedList<E> result = new LinkedList<E>();
+		while(!left.isEmpty() && !right.isEmpty()){
+			//change the direction of this comparison to change the direction of the sort
+			if(left.peek().compareTo(right.peek()) <= 0)
+				result.add(left.remove());
+			else
+				result.add(right.remove());
+		}
+		result.addAll(left);
+		result.addAll(right);
+		return result;
+	}
+
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/StrandSortTest.java b/src/test/java/com/thealgorithms/sorts/StrandSortTest.java
new file mode 100644
index 00000000..f24596e7
--- /dev/null
+++ b/src/test/java/com/thealgorithms/sorts/StrandSortTest.java
@@ -0,0 +1,39 @@
+package com.thealgorithms.sorts;
+
+import org.junit.jupiter.api.Test;
+import static org.junit.jupiter.api.Assertions.*;
+
+import java.util.Arrays;
+import java.util.LinkedList;
+
+
+class StrandSortTest {
+	@Test
+	// valid test case
+	public void StrandSortNonDuplicateTest() {
+		int[] expectedArray = { 1, 2, 3, 4, 5 };
+		LinkedList<Integer> actualList = StrandSort.strandSort(new LinkedList<Integer>(Arrays.asList(3, 1, 2, 4, 5)));
+		int[] actualArray = new int[actualList.size()];
+		for (int i = 0; i < actualList.size(); i++) {
+			actualArray[i] = actualList.get(i);
+		}
+		assertArrayEquals(expectedArray, actualArray);
+
+	}
+
+	@Test
+	// valid test case
+	public void StrandSortDuplicateTest() {
+		int[] expectedArray = { 2, 2, 2, 5, 7 };
+		LinkedList<Integer> actualList = StrandSort.strandSort(new LinkedList<Integer>(Arrays.asList(7, 2, 2, 2, 5)));
+		int[] actualArray = new int[actualList.size()];
+		for (int i = 0; i < actualList.size(); i++) {
+			actualArray[i] = actualList.get(i);
+		}
+		assertArrayEquals(expectedArray, actualArray);
+
+	}
+
+}
+
+