Repository: TheAlgorithms/Java
Pull request #6141 (2025-01-16 09:10:34)

Adding DarkSort Algorithm
This pull request adds the DarkSort algorithm, a randomized sorting algorithm based on the quicksort strategy. The algorithm divides the array around a pivot element, recursively sorts the partitions, and leverages randomization for efficiency. It offers an average-case time complexity of O(n log n) and is useful in scenarios requiring fast sorting with large data sets.

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`.

sahilkumarvalecha: Hi Andrii Siriak
apologies for the confusion earlier dark sort does not deal with strings it only sorts integer based data and is efficient than many other algorithms let me know if you need any further details on this
sahilkumarvalecha: hi I have made changes and now it only accepts integers 

Patch:
diff --git a/src/main/java/com/thealgorithms/sorts/DarkSort.java b/src/main/java/com/thealgorithms/sorts/DarkSort.java
new file mode 100644
index 00000000..4887d7d1
--- /dev/null
+++ b/src/main/java/com/thealgorithms/sorts/DarkSort.java
@@ -0,0 +1,59 @@
+package com.thealgorithms.sorts;
+
+/**
+ * Dark Sort algorithm implementation.
+ *
+ * Dark Sort uses a temporary array to count occurrences of elements and
+ * reconstructs the sorted array based on the counts.
+ */
+class DarkSort {
+
+    /**
+     * Sorts the array using the Dark Sort algorithm.
+     *
+     * @param unsorted the array to be sorted
+     * @return sorted array
+     */
+    public Integer[] sort(Integer[] unsorted) {
+        if (unsorted == null || unsorted.length <= 1) {
+            return unsorted;
+        }
+
+        int max = findMax(unsorted); // Find the maximum value in the array
+
+        // Create a temporary array for counting occurrences
+        int[] temp = new int[max + 1];
+
+        // Count occurrences of each element
+        for (int value : unsorted) {
+            temp[value]++;
+        }
+
+        // Reconstruct the sorted array
+        int index = 0;
+        for (int i = 0; i < temp.length; i++) {
+            while (temp[i] > 0) {
+                unsorted[index++] = i;
+                temp[i]--;
+            }
+        }
+
+        return unsorted;
+    }
+
+    /**
+     * Helper method to find the maximum value in an array.
+     *
+     * @param arr the array
+     * @return the maximum value
+     */
+    private int findMax(Integer[] arr) {
+        int max = arr[0];
+        for (int value : arr) {
+            if (value > max) {
+                max = value;
+            }
+        }
+        return max;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/DarkSortTest.java b/src/test/java/com/thealgorithms/sorts/DarkSortTest.java
new file mode 100644
index 00000000..1df077e2
--- /dev/null
+++ b/src/test/java/com/thealgorithms/sorts/DarkSortTest.java
@@ -0,0 +1,74 @@
+package com.thealgorithms.sorts;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+import static org.junit.jupiter.api.Assertions.assertNull;
+
+import org.junit.jupiter.api.Test;
+
+class DarkSortTest {
+
+    @Test
+    void testSortWithIntegers() {
+        Integer[] unsorted = {5, 3, 8, 6, 2, 7, 4, 1};
+        Integer[] expected = {1, 2, 3, 4, 5, 6, 7, 8};
+
+        DarkSort darkSort = new DarkSort();
+        Integer[] sorted = darkSort.sort(unsorted);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void testEmptyArray() {
+        Integer[] unsorted = {};
+        Integer[] expected = {};
+
+        DarkSort darkSort = new DarkSort();
+        Integer[] sorted = darkSort.sort(unsorted);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void testSingleElementArray() {
+        Integer[] unsorted = {42};
+        Integer[] expected = {42};
+
+        DarkSort darkSort = new DarkSort();
+        Integer[] sorted = darkSort.sort(unsorted);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void testAlreadySortedArray() {
+        Integer[] unsorted = {1, 2, 3, 4, 5};
+        Integer[] expected = {1, 2, 3, 4, 5};
+
+        DarkSort darkSort = new DarkSort();
+        Integer[] sorted = darkSort.sort(unsorted);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void testDuplicateElementsArray() {
+        Integer[] unsorted = {4, 2, 7, 2, 1, 4};
+        Integer[] expected = {1, 2, 2, 4, 4, 7};
+
+        DarkSort darkSort = new DarkSort();
+        Integer[] sorted = darkSort.sort(unsorted);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void testNullArray() {
+        Integer[] unsorted = null;
+
+        DarkSort darkSort = new DarkSort();
+        Integer[] sorted = darkSort.sort(unsorted);
+
+        assertNull(sorted, "Sorting a null array should return null");
+    }
+}