java sorting cheatsheet

package lynchz.datastruc;

import java.util.*;

public class Datastruc {

    public static void main(String[] args) {
        sorting();
    }

    public static void sorting() {
        int n = 1000000;
        int[] arr = new int[n];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(n);
        }

        // array.sort
        long start = System.currentTimeMillis();
        Arrays.sort(arr);
        long end = System.currentTimeMillis();
        System.out.println("Arrays.sort() takes " + (end - start) + "ms");

        // parallel sort
        start = System.currentTimeMillis();
        Arrays.parallelSort(arr);
        end = System.currentTimeMillis();
        System.out.println("Arrays.parallelSort() takes " + (end - start) + "ms");

        // bubblesort
        start = System.currentTimeMillis();
        bubbleSort(arr);
        end = System.currentTimeMillis();
        System.out.println("bubbleSort() takes " + (end - start) + "ms");

        // insertionsort
        start = System.currentTimeMillis();
        insertionSort(arr);
        end = System.currentTimeMillis();
        System.out.println("insertionSort() takes " + (end - start) + "ms");

        // selectionsort
        start = System.currentTimeMillis();
        selectionSort(arr);
        end = System.currentTimeMillis();
        System.out.println("selectionSort() takes " + (end - start) + "ms");

        // mergesort
        start = System.currentTimeMillis();
        mergeSort(arr);
        end = System.currentTimeMillis();
        System.out.println("mergeSort() takes " + (end - start) + "ms");

        // quicksort
        start = System.currentTimeMillis();
        quickSort(arr);
        end = System.currentTimeMillis();
        System.out.println("quickSort() takes " + (end - start) + "ms");

        // heapsort
        start = System.currentTimeMillis();
        heapSort(arr);
        end = System.currentTimeMillis();
        System.out.println("heapSort() takes " + (end - start) + "ms");

        // shellsort
        start = System.currentTimeMillis();
        shellSort(arr);
        end = System.currentTimeMillis();
        System.out.println("shellSort() takes " + (end - start) + "ms");

        // radixsort
        start = System.currentTimeMillis();
        radixSort(arr);
        end = System.currentTimeMillis();
        System.out.println("radixSort() takes " + (end - start) + "ms");

        // countingsort
        start = System.currentTimeMillis();
        countingSort(arr);
        end = System.currentTimeMillis();
        System.out.println("countingSort() takes " + (end - start) + "ms");

        // bucketsort
        start = System.currentTimeMillis();
        bucketSort(arr);
        end = System.currentTimeMillis();
        System.out.println("bucketSort() takes " + (end - start) + "ms");

        // combsort
        start = System.currentTimeMillis();
        combSort(arr);
        end = System.currentTimeMillis();
        System.out.println("combSort() takes " + (end - start) + "ms");

        // pigeonholeSort
        start = System.currentTimeMillis();
        pigeonholeSort(arr);
        end = System.currentTimeMillis();
        System.out.println("pigeonholeSort() takes " + (end - start) + "ms");

        // cocktailsort
        start = System.currentTimeMillis();
        cocktailSort(arr);
        end = System.currentTimeMillis();
        System.out.println("cocktailSort() takes " + (end - start) + "ms");

        // gnomeSort
        start = System.currentTimeMillis();
        gnomeSort(arr);
        end = System.currentTimeMillis();
        System.out.println("gnomeSort() takes " + (end - start) + "ms");

        // cycleSort
        start = System.currentTimeMillis();
        cycleSort(arr);
        end = System.currentTimeMillis();
        System.out.println("cycleSort() takes " + (end - start) + "ms");

        // pancakeSort
        start = System.currentTimeMillis();
        pancakeSort(arr);
        end = System.currentTimeMillis();
        System.out.println("pancakeSort() takes " + (end - start) + "ms");

        // bitonicSort
        start = System.currentTimeMillis();
        bitonicSort(arr, 0);
        end = System.currentTimeMillis();
        System.out.println("bitonicSort() takes " + (end - start) + "ms");

        // stoogeSort
        start = System.currentTimeMillis();
        stoogeSort(arr, 0, 0);
        end = System.currentTimeMillis();
        System.out.println("stoogeSort() takes " + (end - start) + "ms");

        // bogoSort
        start = System.currentTimeMillis();
        bogoSort(arr);
        end = System.currentTimeMillis();
        System.out.println("bogoSort() takes " + (end - start) + "ms");

        // beadSort
        start = System.currentTimeMillis();
        beadSort(arr);
        end = System.currentTimeMillis();
        System.out.println("beadSort() takes " + (end - start) + "ms");

        // blockSort
        start = System.currentTimeMillis();
        blockSort(arr);
        end = System.currentTimeMillis();
        System.out.println("blockSort() takes " + (end - start) + "ms");

        // flashSort
        start = System.currentTimeMillis();
        flashSort(arr);
        end = System.currentTimeMillis();
        System.out.println("flashSort() takes " + (end - start) + "ms");

        // smoothSort
        start = System.currentTimeMillis();
        smoothSort(arr);
        end = System.currentTimeMillis();
        System.out.println("smoothSort() takes " + (end - start) + "ms");

        // strandSort
        start = System.currentTimeMillis();
        strandSort(arr);
        end = System.currentTimeMillis();
        System.out.println("strandSort() takes " + (end - start) + "ms");
    }

    static void bubbleSort(int[] arr) {
        int n = arr.length;
        int temp = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < (n - i); j++) {
                if (arr[j - 1] > arr[j]) {
                    // swap elements
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }

            }
        }

    }

    static void insertionSort(int array[]) {
        int n = array.length;
        for (int j = 1; j < n; j++) {
            int key = array[j];
            int i = j - 1;
            while ((i > -1) && (array[i] > key)) {
                array[i + 1] = array[i];
                i--;
            }
            array[i + 1] = key;
        }
    }

    static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[index]) {
                    index = j;// searching for lowest index
                }
            }
            int smallerNumber = arr[index];
            arr[index] = arr[i];
            arr[i] = smallerNumber;
        }
    }

    static void mergeSort(int[] arr) {
        if (arr.length > 1) {
            // Merge sort the first half
            int[] firstHalf = new int[arr.length / 2];
            System.arraycopy(arr, 0, firstHalf, 0, arr.length / 2);
            mergeSort(firstHalf);

            // Merge sort the second half
            int secondHalfLength = arr.length - arr.length / 2;
            int[] secondHalf = new int[secondHalfLength];
            System.arraycopy(arr, arr.length / 2, secondHalf, 0, secondHalfLength);
            mergeSort(secondHalf);

            // Merge firstHalf with secondHalf into arr
            merge(firstHalf, secondHalf, arr);
        }
    }

            private static void merge(int[] firstHalf, int[] secondHalf, int[] arr) {
                int current1 = 0; // Current index in firstHalf
                int current2 = 0; // Current index in secondHalf
                int current3 = 0; // Current index in arr

                while (current1 < firstHalf.length && current2 < secondHalf.length) {
                    if (firstHalf[current1] < secondHalf[current2])
                        arr[current3++] = firstHalf[current1++];
                    else
                        arr[current3++] = secondHalf[current2++];
                }

                while (current1 < firstHalf.length)
                    arr[current3++] = firstHalf[current1++];

                while (current2 < secondHalf.length)
                    arr[current3++] = secondHalf[current2++];
            }

    static void quickSort(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0); // Push the starting index of the array
        stack.push(arr.length - 1); // Push the ending index of the array

        while (!stack.isEmpty()) {
            int high = stack.pop(); // Pop the ending index of the subarray
            int low = stack.pop(); // Pop the starting index of the subarray

            if (high > low) { // If there are at least two elements in the subarray
                int pivotIndex = partition(arr, low, high); // Partition the subarray around a pivot element
                stack.push(low); // Push the starting index of the left subarray
                stack.push(pivotIndex - 1); // Push the ending index of the left subarray
                stack.push(pivotIndex + 1); // Push the starting index of the right subarray
                stack.push(high); // Push the ending index of the right subarray
            }
        }
    }

            private static int partition(int[] arr, int low, int high) {
                int pivot = arr[high]; // Choose the last element of the subarray as the pivot
                int i = low - 1; // Initialize the index of the smaller element

                for (int j = low; j < high; j++) {
                    if (arr[j] < pivot) { // If the current element is smaller than the pivot
                        i++; // Increment the index of the smaller element
                        int temp = arr[i]; // Swap arr[i] and arr[j]
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }

                int temp = arr[i + 1]; // Swap arr[i+1] and arr[high] (or the pivot)
                arr[i + 1] = arr[high];
                arr[high] = temp;

                return i + 1; // Return the index of the pivot element
            }

            static void heapSort(int[] arr) {
                // Create a Heap of integers
                Heap<Integer> heap = new Heap<Integer>();

                // Add elements to the heap
                for (int i = 0; i < arr.length; i++)
                    heap.add(arr[i]);

                // Remove elements from the heap
                for (int i = arr.length - 1; i >= 0; i--)
                    arr[i] = heap.remove();
            }

            private static class Heap<E extends Comparable<E>> {
                private java.util.ArrayList<E> list = new java.util.ArrayList<E>();

                /** Create a default heap */
                public Heap() {
                }

                /** Create a heap from an array of objects */
                public Heap(E[] objects) {
                    for (int i = 0; i < objects.length; i++)
                        add(objects[i]);
                }

                /** Add a new object into the heap */
                public void add(E newObject) {
                    list.add(newObject); // Append to the heap
                    int currentIndex = list.size() - 1; // The index of the last node

                    while (currentIndex > 0) {
                        int parentIndex = (currentIndex - 1) / 2;
                        // Swap if the current object is greater than its parent
                        if (list.get(currentIndex).compareTo(
                                list.get(parentIndex)) > 0) {
                            E temp = list.get(currentIndex);
                            list.set(currentIndex, list.get(parentIndex));
                            list.set(parentIndex, temp);
                        } else
                            break; // the tree is a heap now

                        currentIndex = parentIndex;
                    }
                }

                /** Remove the root from the heap */
                public E remove() {
                    if (list.size() == 0)
                        return null;

                    E removedObject = list.get(0);
                    list.set(0, list.get(list.size() - 1));
                    list.remove(list.size() - 1);

                    int currentIndex = 0;
                    while (currentIndex < list.size()) {
                        int leftChildIndex = 2 * currentIndex + 1;
                        int rightChildIndex = 2 * currentIndex + 2;

                        // Find the maximum between two children
                        if (leftChildIndex >= list.size())
                            break; // The tree is a heap
                        int maxIndex = leftChildIndex;
                        if (rightChildIndex < list.size()) {
                            if (list.get(maxIndex).compareTo(
                                    list.get(rightChildIndex)) < 0) {
                                maxIndex = rightChildIndex;
                            }
                        }

                        // Swap if the current node is less than the maximum
                        if (list.get(currentIndex).compareTo(
                                list.get(maxIndex)) < 0) {
                            E temp = list.get(maxIndex);
                            list.set(maxIndex, list.get(currentIndex));
                            list.set(currentIndex, temp);
                            currentIndex = maxIndex;
                        } else
                            break; // The tree is a heap
                    }
                    return removedObject;
                }
    }

    static void shellSort(int[] arr) {
        int n = arr.length;
        int gap = n / 2;
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int j = i;
                int temp = arr[i];
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
            gap /= 2;
        }
    }

    static void radixSort(int[] arr) {
        // Find the largest number to know number of digits
        int max = arr[0];
        for (int i = 1; i < arr.length; i++)
            if (arr[i] > max)
                max = arr[i];

        // Do counting sort for every digit. Note that instead
        // of passing digit number, exp is passed. exp is 10^i
        // where i is current digit number
        for (int exp = 1; max / exp > 0; exp *= 10)
            countingSort(arr, exp);
    }

    private static void countingSort(int[] arr, int exp) {
        int[] output = new int[arr.length]; // output array
        int[] count = new int[10];
        Arrays.fill(count, 0);

        // Store count of occurrences in count[]
        for (int i = 0; i < arr.length; i++)
            count[(arr[i] / exp) % 10]++;

        // Change count[i] so that count[i] now contains actual
        // position of this digit in output[]
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];

        // Build the output array
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        // Copy the output array to arr[], so that arr[] now
        // contains sorted numbers according to current digit
        for (int i = 0; i < arr.length; i++)
            arr[i] = output[i];
    }

    static void countingSort(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max)
                max = arr[i];
            if (arr[i] < min)
                min = arr[i];
        }

        int[] count = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++)
            count[arr[i] - min]++;

        int z = 0;
        for (int i = min; i <= max; i++)
            while (count[i - min]-- > 0)
                arr[z++] = i;
    }

    static void bucketSort(int[] arr) {
        int maxVal = arr[0];
        int minVal = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxVal)
                maxVal = arr[i];
            if (arr[i] < minVal)
                minVal = arr[i];
        }

        int bucketLen = (maxVal - minVal) / arr.length + 1;
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>(bucketLen);
        for (int i = 0; i < bucketLen; i++) {
            buckets.add(new ArrayList<Integer>());
        }

        // distribute the numbers into buckets
        for (int i = 0; i < arr.length; i++) {
            buckets.get((arr[i] - minVal) / arr.length).add(arr[i]);
        }

        // sort each bucket
        for (int i = 0; i < buckets.size(); i++) {
            Collections.sort(buckets.get(i));
        }

        // concatenate the result
        int idx = 0;
        for (int i = 0; i < buckets.size(); i++) {
            for (int j = 0; j < buckets.get(i).size(); j++) {
                arr[idx++] = buckets.get(i).get(j);
            }
        }
    }

    static void combSort(int[] arr) {
        int gap = arr.length;
        boolean swapped = true;
        while (gap != 1 || swapped) {
            // Find next gap
            gap = getNextGap(gap);

            // Initialize swapped as false so that we can
            // check if swap happened or not
            swapped = false;

            // Compare all elements with current gap
            for (int i = 0; i < arr.length - gap; i++) {
                if (arr[i] > arr[i + gap]) {
                    // Swap arr[i] and arr[i+gap]
                    int temp = arr[i];
                    arr[i] = arr[i + gap];
                    arr[i + gap] = temp;

                    // Set swapped
                    swapped = true;
                }
            }
        }
    }

            private static int getNextGap(int gap) {
                // Shrink gap by Shrink factor
                gap = (gap * 10) / 13;

                if (gap < 1)
                    return 1;
                return gap;
            }

    static void pigeonholeSort(int[] arr) {
        int min = arr[0];
        int max = arr[0];
        int range, i, j, index;

        for (int a = 0; a < arr.length; a++) {
            if (arr[a] > max)
                max = arr[a];
            if (arr[a] < min)
                min = arr[a];
        }

        range = max - min + 1;
        int[] phole = new int[range];
        Arrays.fill(phole, 0);

        for (i = 0; i < arr.length; i++)
            phole[arr[i] - min]++;

        index = 0;

        for (j = 0; j < range; j++)
            while (phole[j]-- > 0)
                arr[index++] = j + min;

    }

    static void cocktailSort(int[] arr) {
        boolean swapped = true;
        int start = 0;
        int end = arr.length;

        while (swapped == true) {
            // reset the swapped flag on entering the loop,
            // because it might be true from a previous
            // iteration.
            swapped = false;

            // loop from left to right same as the bubble
            // sort
            for (int i = start; i < end - 1; ++i) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    swapped = true;
                }
            }

            // if nothing moved, then array is sorted.
            if (swapped == false)
                break;

            // otherwise, reset the swapped flag so that it
            // can be used in the next stage
            swapped = false;

            // move the end point back by one, because
            // item at the end is in its rightful spot
            end = end - 1;

            // from right to left, doing the
            // same comparison as in the previous stage
            for (int i = end - 1; i >= start; i--) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    swapped = true;
                }
            }

            // increase the starting point, because
            // the last stage would have moved the next
            // smallest number to its rightful spot.
            start = start + 1;
        }
    }

    static void gnomeSort(int[] arr) {
        int index = 0;

        while (index < arr.length) {
            if (index == 0)
                index++;
            if (arr[index] >= arr[index - 1])
                index++;
            else {
                int temp = 0;
                temp = arr[index];
                arr[index] = arr[index - 1];
                arr[index - 1] = temp;
                index--;
            }
        }
        return;
    }

    static void cycleSort(int[] arr) {
        int writes = 0;

        // Loop through the array to find cycles to rotate.
        for (int cycleStart = 0; cycleStart <= arr.length - 2; cycleStart++) {
            // initialize item as starting point.
            int item = arr[cycleStart];

            // Find where to put the item.
            int pos = cycleStart;
            for (int i = cycleStart + 1; i < arr.length; i++)
                if (arr[i] < item)
                    pos++;

            // If the item is already there, this is not a cycle.
            if (pos == cycleStart)
                continue;

            // Otherwise, put the item there or right after any duplicates.
            while (item == arr[pos])
                pos += 1;
            int temp = item;
            item = arr[pos];
            arr[pos] = temp;
            writes++;

            // Rotate the rest of the cycle.
            while (pos != cycleStart) {
                pos = cycleStart;

                // Find where to put the item.
                for (int i = cycleStart + 1; i < arr.length; i++)
                    if (arr[i] < item)
                        pos += 1;

                // Put the item there or right after any duplicates.
                while (item == arr[pos])
                    pos += 1;
                temp = item;
                item = arr[pos];
                arr[pos] = temp;
                writes++;
            }
        }
    }

    static void pancakeSort(int[] arr) {
        // Start from the complete array and one by one
        // reduce current size by one
        for (int curr_size = arr.length; curr_size > 1; --curr_size) {
            // Find index of the maximum element in
            // arr[0..curr_size-1]
            int mi = findMax(arr, curr_size);

            // Move the maximum element to end of current
            // array if it's not already at the end
            if (mi != curr_size - 1) {
                // To move at the end, first move maximum
                // number to beginning
                flip(arr, mi);

                // Now move the maximum number to end by
                // reversing current array
                flip(arr, curr_size - 1);
            }
        }
    }

            private static int findMax(int[] arr, int curr_size) {
                int mi, i;
                for (mi = 0, i = 0; i < curr_size; ++i)
                    if (arr[i] > arr[mi])
                        mi = i;
                return mi;
            }

            private static void flip(int[] arr, int i) {
                int temp, start = 0;
                while (start < i) {
                    temp = arr[start];
                    arr[start] = arr[i];
                    arr[i] = temp;
                    start++;
                    i--;
                }
            }

    static void bitonicSort(int[] arr, int up) {
        // Start the bitonic merge process with the entire array
        // up is 1 for ascending and 0 for descending
        bitonicMerge(arr, 0, arr.length, up);
    }

            private static void bitonicMerge(int[] arr, int low, int cnt, int up) {
                if (cnt > 1) {
                    int k = cnt / 2;

                    // Compare and swap elements in the left and right subarrays
                    for (int i = low; i < low + k; i++)
                        compAndSwap(arr, i, i + k, up);

                    // Recursively merge the left and right subarrays
                    bitonicMerge(arr, low, k, up);
                    bitonicMerge(arr, low + k, k, up);
                }
            }

            private static void compAndSwap(int[] arr, int i, int j, int up) {
                if ((arr[i] > arr[j] && up == 1) || (arr[i] < arr[j] && up == 0)) {
                    // Swap the elements if they are out of order based on the value of the 'up'
                    // flag
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }

    static void stoogeSort(int[] arr, int l, int h) {
        if (l >= h)
            return;

        // If first element is smaller than last, swap them
        if (arr[l] > arr[h]) {
            int temp = arr[l];
            arr[l] = arr[h];
            arr[h] = temp;
        }

        // If there are more than 2 elements in the array
        if (h - l + 1 > 2) {
            int t = (h - l + 1) / 3;

            // Recursively sort first 2/3 elements
            stoogeSort(arr, l, h - t);

            // Recursively sort last 2/3 elements
            stoogeSort(arr, l + t, h);

            // Recursively sort first 2/3 elements again to confirm
            stoogeSort(arr, l, h - t);
        }
    }

    static void bogoSort(int[] arr) {
        // if array is not sorted then shuffle the
        // array again
        while (isSorted(arr) == false)
            shuffle(arr);
    }

            private static boolean isSorted(int[] arr) {
                // check if array is sorted or not
                for (int i = 0; i < arr.length - 1; i++)
                    if (arr[i] > arr[i + 1])
                        return false;
                return true;
            }

            private static void shuffle(int[] arr) {
                // Math.random() returns a double positive
                // value, greater than or equal to 0.0 and
                // less than 1.0.
                for (int i = 0; i < arr.length; i++) {
                    int r = (int) (Math.random() * (arr.length - i));
                    int temp = arr[i];
                    arr[i] = arr[r];
                    arr[r] = temp;
                }
    }

    static void beadSort(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++)
            if (arr[i] > max)
                max = arr[i];

        // Create an array of beads, each bead
        // being 1 unit long
        int[][] beads = new int[max][arr.length];

        // Mark the beads
        for (int i = 0; i < arr.length; i++)
            for (int j = 0; j < arr[i]; j++)
                beads[j][i] = 1;

        // Put the beads in order
        for (int i = 0; i < max; i++)
            for (int j = 0, sum = 0; j < arr.length; j++) {
                sum += beads[i][j];
                beads[i][j] = 0;
                arr[j] = sum;
            }
    }

    static void blockSort(int[] arr) {
        // Find the maximum value in arr[]
        int n = arr.length;
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > max)
                max = arr[i];
            if (arr[i] < min)
                min = arr[i];
        }
        int range = max - min + 1;

        // Create an array of vectors. Size of
        // array is equal to range. Each vector
        // represents a bucket.
        @SuppressWarnings("unchecked")
        Vector<Integer>[] bucket = new Vector[range];

        // Initialize each bucket
        for (int i = 0; i < bucket.length; i++)
            bucket[i] = new Vector<>();

        // Traverse the input array and put every
        // element in its respective bucket
        for (int i = 0; i < n; i++) {
            bucket[arr[i] - min].add(arr[i]);
        }

        // Traverse the buckets and put all elements
        // back into arr[]
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            for (int j = 0; j < bucket[i].size(); j++) {
                arr[index++] = bucket[i].get(j);
            }
        }
    }

    static void flashSort(int[] arr) {
        int n = arr.length;
        int m = (int) (0.45 * n);
        int[] l = new int[m];

        for (int i = 0; i < m; i++)
            l[i] = 0;

        // Find the maximum and minimum values
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > max)
                max = arr[i];
            if (arr[i] < min)
                min = arr[i];
        }

        // Find the range
        int range = max - min;

        // Find the flash value
        int flash = (int) (m - 1) / range;

        // Distribute the elements
        for (int i = 0; i < n; i++) {
            int index = (int) (flash * (arr[i] - min));
            l[index]++;
        }

        // Find the cumulative distribution
        for (int i = 1; i < m; i++)
            l[i] += l[i - 1];

        // Shift the elements
        int hold = arr[n - 1];
        int j = 0;
        int k = m - 1;
        int move = 0;
        while (move < (n - 1)) {
            while (j > (l[k] - 1)) {
                j++;
                k = (int) (flash * (arr[j] - min));
            }
            hold = arr[j];
            while (j == l[k]) {
                k = (int) (flash * (hold - min));
                int temp = arr[l[k] - 1];
                arr[l[k] - 1] = hold;
                hold = temp;
                l[k]--;
                move++;
            }
        }
    }

    static void smoothSort(int[] arr) {
        int n = arr.length; // Get the length of the array
        int temp; // Declare a temporary variable for swapping values

        // Sort pairs of elements in the array in ascending order
        for (int i = 0; i < n; i += 2) {
            // Swap the values of the current element and the previous element if the
            // previous element is greater
            if (i != 0 && arr[i] < arr[i - 1]) {
                temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
            }
            // Swap the values of the current element and the next element if the next
            // element is smaller
            if (i != n - 1 && arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }

        boolean isSorted = false; // Set a flag to track whether the array is sorted

        // Keep sorting the array until it is fully sorted
        while (!isSorted) {
            isSorted = true; // Assume the array is sorted initially

            // Sort sub-arrays of increasing size using the "smoothsort" algorithm
            for (int i = 1; i <= n - 2; i = 2 * i) { // i is the size of the sub-array being sorted
                for (int j = 0; j < n - 2; j += 2 * i) { // j is the starting index of the sub-array
                    int sub_array_length = 2 * i; // Length of the sub-array
                    int sub_array_middle = j + i - 1; // Middle index of the sub-array
                    int k = 0; // Index of the sorted array
                    int left = j; // Starting index of the left sub-array
                    int right = j + i; // Starting index of the right sub-array
                    int[] sorted = new int[sub_array_length]; // Temporary array to hold the sorted values

                    // Merge the two sub-arrays into the sorted array
                    while (left <= sub_array_middle && right <= (j + sub_array_length - 1)) {
                        if (arr[left] < arr[right]) {
                            sorted[k] = arr[left];
                            left++;
                        } else {
                            sorted[k] = arr[right];
                            right++;
                        }
                        k++;
                    }
                    // Add any remaining values from the left sub-array to the sorted array
                    if (left > sub_array_middle) {
                        for (int l = right; l <= (j + sub_array_length - 1); l++) {
                            sorted[k] = arr[l];
                            k++;
                        }
                    }
                    // Add any remaining values from the right sub-array to the sorted array
                    else {
                        for (int l = left; l <= sub_array_middle; l++) {
                            sorted[k] = arr[l];
                            k++;
                        }
                    }

                    // Copy the sorted values back into the original array
                    for (int l = j; l <= (j + sub_array_length - 1); l++) {
                        arr[l] = sorted[l - j];
                    }
                }
            }
        }
    }

    static void strandSort(int[] arr) {
        // Get the length of the input array
        int n = arr.length;
        // Create a temporary array to store the input array
        int[] temp = new int[n];
        // Create a sorted array to keep track of which elements have been sorted
        int[] sorted = new int[n];
        // Initialize the temporary array with the input array, and set all elements in
        // the sorted array to 0
        int index = 0;
        for (int i = 0; i < n; i++) {
            temp[i] = arr[i];
            sorted[i] = 0;
        }
        // Continue iterating until all elements have been sorted
        while (index != n) {
            // Get the index of the minimum element in the temporary array that hasn't been
            // sorted yet
            int min_index = getMin(temp, sorted);
            // Add the minimum element to the output array, and mark it as sorted
            arr[index] = temp[min_index];
            sorted[min_index] = 1;
            index++;
        }
    }

            // Helper function to get the index of the minimum element in an array that
            // hasn't been sorted yet
            private static int getMin(int[] temp, int[] sorted) {
                // Initialize the minimum value to the maximum possible integer value, and the
                // index to -1
                int min = Integer.MAX_VALUE;
                int index = -1;
                // Iterate through the array and find the minimum value that hasn't been sorted
                // yet
                for (int i = 0; i < temp.length; i++) {
                    if (temp[i] < min && sorted[i] == 0) {
                        min = temp[i];
                        index = i;
                    }
                }
                // Return the index of the minimum element
                return index;
    }

}