Repository: TheAlgorithms/Java
Pull request #3780 (2022-11-30 15:00:27)

Tim Sort (fix): simple implementation
<!-- For completed items, change [ ] to [x] -->

- [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.



Patch:
diff --git a/src/main/java/com/thealgorithms/sorts/InsertionSort.java b/src/main/java/com/thealgorithms/sorts/InsertionSort.java
index 594379a5..e9031cb9 100644
--- a/src/main/java/com/thealgorithms/sorts/InsertionSort.java
+++ b/src/main/java/com/thealgorithms/sorts/InsertionSort.java
@@ -15,9 +15,15 @@ class InsertionSort implements SortAlgorithm {
      */
     @Override
     public <T extends Comparable<T>> T[] sort(T[] array) {
-        for (int i = 1; i < array.length; i++)
-            for (int j = i; j > 0 && less(array[j], array[j - 1]); j--)
+        return sort(array, 0, array.length);
+    }
+
+    public <T extends Comparable<T>> T[] sort(T[] array, int lo, int hi) {
+        for (int i = lo; i < hi; i++) {
+            for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {
                 swap(array, j, j - 1);
+            }
+        }
         return array;
     }
 
diff --git a/src/main/java/com/thealgorithms/sorts/TimSort.java b/src/main/java/com/thealgorithms/sorts/TimSort.java
index e2961e15..41337bc5 100644
--- a/src/main/java/com/thealgorithms/sorts/TimSort.java
+++ b/src/main/java/com/thealgorithms/sorts/TimSort.java
@@ -1,224 +1,52 @@
 package com.thealgorithms.sorts;
 
-import java.util.Random;
+import static com.thealgorithms.sorts.SortUtils.less;
 
 /**
- * @author [Hemanth Kotagiri](https://github.com/hemanth-kotagiri)
- * @see [Tim Sort](https://en.wikipedia.org/wiki/Tim_sort)
+ * This is simplified TimSort algorithm implementation. The original one is more complicated.
+ * <p>
+ * For more details @see <a href="https://en.wikipedia.org/wiki/Timsort">TimSort Algorithm</a>
  */
-class TimSort {
+class TimSort implements SortAlgorithm {
+    private static final int SUB_ARRAY_SIZE = 32;
+    @SuppressWarnings("rawtypes")
+    private static Comparable[] aux;
 
-    int array[];
-    int array_length;
-    int RUN = 32;
+    @Override
+    public <T extends Comparable<T>> T[] sort(T[] a) {
+        int n = a.length;
 
-    /**
-     * @brief A constructor which takes in the array specified by the user.
-     * @param array : Array given by the user.
-     */
-    public TimSort(int[] array) {
-        this.array = array;
-        this.array_length = array.length;
-    }
-
-    /**
-     * @brief A constructor which takes in an array length and randomly
-     * initializes an array.
-     * @param array_length length given by the user.
-     */
-    public TimSort(int array_length) {
-        Random rand = new Random();
-
-        this.array_length = array_length;
-        this.array = new int[this.array_length];
-
-        for (int i = 0; i < this.array_length; i++) {
-            int random_number = rand.nextInt(1000);
-            this.array[i] = random_number;
+        InsertionSort insertionSort = new InsertionSort();
+        for (int i = 0; i < n; i += SUB_ARRAY_SIZE) {
+            insertionSort.sort(a, i, Math.min(i + SUB_ARRAY_SIZE, n));
         }
-    }
-
-    /**
-     * @brief A method to change the size of the run.
-     * @param run : Value specified by the user to change the run.
-     */
-    public void change_run(int run) {
-        this.RUN = run;
-    }
-
-    /**
-     * @brief A default constructor when no parameters are given. Initializes
-     * the array length to be 100. Generates a random number array of size 100.
-     */
-    public TimSort() {
-        this.array_length = 100;
-        this.array = new int[this.array_length];
-
-        Random rand = new Random();
-        for (int i = 0; i < this.array_length; i++) {
-            int random_number = rand.nextInt(1000);
-            this.array[i] = random_number;
-        }
-    }
 
-    /**
-     * @brief Performs Insertion Sort Algorithm on given array with bounded
-     * indices.
-     * @param array: The array on which the algorithm is to be performed.
-     * @param start_idx: The starting index from which the algorithm is to be
-     * performed.
-     * @param end_idx: The ending index at which the algorithm needs to stop
-     * sorting.
-     */
-    public void insertion_sort(int[] array, int start_idx, int end_idx) {
-        for (int i = start_idx; i <= end_idx; i++) {
-            int current_element = array[i];
-            int j = i - 1;
-            while (j >= start_idx && array[j] > current_element) {
-                array[j + 1] = array[j];
-                j--;
-            }
-            array[j + 1] = current_element;
-        }
-    }
-
-    /**
-     * @brief A method to merge two runs(chunks of array).
-     * @param array: The origin array which is to be sorted.
-     * @param start: Starting index of the first run(chunk).
-     * @param mid: The ending index of the first run(chunk).
-     * @param end: Ending index of the second run(chunk).
-     */
-    public void merge_runs(int array[], int start, int mid, int end) {
-        int first_array_size = mid - start + 1, second_array_size = end - mid;
-        int array1[] = new int[first_array_size], array2[] = new int[second_array_size];
-        int i = 0, j = 0, k = 0;
-
-        // Building the two sub arrays from the array to merge later
-        for (i = 0; i < first_array_size; i++) {
-            array1[i] = array[start + i];
-        }
-        for (i = 0; i < second_array_size; i++) {
-            array2[i] = array[mid + 1 + i];
-        }
-
-        i = 0;
-        j = 0;
-        k = start;
-
-        while (i < first_array_size && j < second_array_size) {
-            if (array1[i] <= array2[j]) {
-                array[k] = array1[i];
-                i++;
-            } else {
-                array[k] = array2[j];
-                j++;
+        aux = new Comparable[n];
+        for (int sz = SUB_ARRAY_SIZE; sz < n; sz = sz + sz) {
+            for (int lo = 0; lo < n - sz; lo += sz + sz) {
+                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, n - 1));
             }
-            k++;
         }
 
-        while (i < first_array_size) {
-            array[k] = array1[i];
-            k++;
-            i++;
-        }
-
-        while (j < second_array_size) {
-            array[k] = array2[j];
-            k++;
-            j++;
-        }
+        return a;
     }
 
-    /**
-     * @brief Tim Sort Algorithm method.
-     */
-    public void algorithm() {
-        // Before Sorting
-        System.out.println("Before sorting the array: ");
-        this.showArrayElements();
-        System.out.println();
-
-        // Applying insertion sort on RUNS.
-        for (int i = 0; i < this.array_length; i += this.RUN) {
-            this.insertion_sort(
-                    this.array,
-                    i,
-                    Math.min(i + this.RUN, (this.array_length - 1))
-                );
-        }
-
-        for (
-            int split = this.RUN;
-            split < this.array_length;
-            split = 2 * split
-        ) {
-            for (
-                int start_idx = 0;
-                start_idx < this.array_length;
-                start_idx += 2 * split
-            ) {
-                int mid = start_idx + split - 1;
-                int end_idx = Math.min(
-                    (start_idx + 2 * split - 1),
-                    (this.array_length - 1)
-                );
+    @SuppressWarnings("unchecked")
+    private static <T extends Comparable<T>> void merge(T[] a, int lo, int mid, int hi) {
+        int i = lo, j = mid + 1;
+        System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
 
-                this.merge_runs(this.array, start_idx, mid, end_idx);
+        for (int k = lo; k <= hi; k++) {
+            if (j > hi) {
+                a[k] = (T) aux[i++];
+            } else if (i > mid) {
+                a[k] = (T) aux[j++];
+            } else if (less(aux[j], aux[i])) {
+                a[k] = (T) aux[j++];
+            } else {
+                a[k] = (T) aux[i++];
             }
         }
-        // After sorting
-        System.out.println("After sorting the array: ");
-        this.showArrayElements();
-        System.out.println();
-    }
-
-    /**
-     * @brief A method to show the elements inside the array.
-     */
-    public void showArrayElements() {
-        for (int i = 0; i < this.array.length; i++) {
-            System.out.print(this.array[i] + " ");
-        }
-        System.out.println();
     }
 
-    /**
-     * @brief A method to test the sorting algorithm
-     */
-    static void test() {
-        int[] array = { 4, 1, 3, 17, 12, 11, 8 };
-        TimSort sorterObj1 = new TimSort();
-        TimSort sorterObj2 = new TimSort(50);
-        TimSort sorterObj3 = new TimSort(array);
-
-        sorterObj1.algorithm();
-        sorterObj2.algorithm();
-        sorterObj3.algorithm();
-
-        // Testing the first array
-        for (int i = 0; i < sorterObj1.array_length - 1; i++) {
-            assert (
-                (sorterObj1.array[i] <= sorterObj1.array[i + 1])
-            ) : "Array is not sorted";
-        }
-
-        // Testing the second array.
-        for (int i = 0; i < sorterObj2.array_length - 1; i++) {
-            assert (
-                (sorterObj2.array[i] <= sorterObj2.array[i + 1])
-            ) : "Array is not sorted";
-        }
-
-        // Testing the third array.
-        for (int i = 0; i < sorterObj3.array_length - 1; i++) {
-            assert (
-                (sorterObj3.array[i] <= sorterObj3.array[i + 1])
-            ) : "Array is not sorted";
-        }
-    }
-
-    public static void main(String[] args) {
-        test();
-    }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/sorts/TimSortTest.java b/src/test/java/com/thealgorithms/sorts/TimSortTest.java
new file mode 100644
index 00000000..b319aa23
--- /dev/null
+++ b/src/test/java/com/thealgorithms/sorts/TimSortTest.java
@@ -0,0 +1,95 @@
+package com.thealgorithms.sorts;
+
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class TimSortTest {
+
+    private TimSort timSort;
+
+    @BeforeEach
+    void setUp() {
+        timSort = new TimSort();
+    }
+
+    @Test
+    void shouldAcceptWhenEmptyArrayIsPassed() {
+        Integer [] array = new Integer[]{};
+        Integer [] expected = new Integer[]{};
+
+        Integer []sorted = timSort.sort(array);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void shouldAcceptWhenSingleValuedArrayIsPassed() {
+        Integer [] array = new Integer[]{2};
+        Integer [] expected = new Integer[]{2};
+
+        Integer [] sorted = timSort.sort(array);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void shouldAcceptWhenArrayWithAllPositiveValuesIsPassed() {
+        Integer [] array = new Integer[]{60, 7, 55, 9, 999, 3};
+        Integer [] expected = new Integer[]{3, 7, 9, 55, 60, 999};
+
+        Integer [] sorted = timSort.sort(array);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void shouldAcceptWhenArrayWithAllNegativeValuesIsPassed() {
+        Integer [] array = new Integer[]{-60, -7, -55, -9, -999, -3};
+        Integer [] expected = new Integer[]{-999, -60, -55, -9, -7, -3};
+
+        Integer [] sorted = timSort.sort(array);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void shouldAcceptWhenArrayWithRealNumberValuesIsPassed() {
+        Integer [] array = new Integer[]{60, -7, 55, 9, -999, -3};
+        Integer [] expected = new Integer[]{-999, -7, -3, 9, 55, 60};
+
+        Integer [] sorted = timSort.sort(array);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void shouldAcceptWhenArrayWithDuplicateValueIsPassed() {
+        Integer [] array = new Integer[]{60, 7, 55, 55, 999, 3};
+        Integer [] expected = new Integer[]{3, 7, 55, 55, 60, 999};
+
+        Integer [] sorted = timSort.sort(array);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void shouldAcceptWhenStringValueArrayIsPassed() {
+        String[] array = {"z", "a", "x", "b", "y"};
+        String[] expected = {"a", "b", "x", "y", "z"};
+
+        String[] sorted = timSort.sort(array);
+
+        assertArrayEquals(expected, sorted);
+    }
+
+    @Test
+    void shouldAcceptWhenRandomArrayIsPassed() {
+        int randomSize = SortUtilsRandomGenerator.generateInt(10_000);
+        Double[] array = SortUtilsRandomGenerator.generateArray(randomSize);
+        Double[] sorted = timSort.sort(array);
+        assertTrue(SortUtils.isSorted(sorted));
+    }
+
+}