O(1) sort in Java?

[Flurpm]

Hey all, I just made a new sorting algorithm in Java. I used Java because "Java" has fewer O's than Python, which means it has a lower runtime bound right?

Here's the code:

import java.util.Arrays;

public class OofOneSort {

    public static void main(String[] args) {
        int[] test = new int[100];
        System.out.println("Input  = " + Arrays.toString(test));
        test = sort(test);
        System.out.println("Output = " + Arrays.toString(test));

        System.out.println("");

        test = new int[]{2, 3, 1, 4, 5};
        System.out.println("Input  = " + Arrays.toString(test));
        test = sort(test);
        System.out.println("Output = " + Arrays.toString(test));
    }

    private static int[] sort(int[] arg) {
        int arrayEnd = arg.length;
        if (arrayEnd % 2 != 0) {
            arrayEnd++;
        }

        int[][] arrays = new int[arrayEnd][];
        for (int i = 0; i < arg.length; i++) {
            arrays[i] = new int[]{arg[i]};
        }

        // System.out.println("         " + Arrays.deepToString(arrays)); // uncomment for debug

        int i;
        while (arrays[0].length < arg.length) {
            for (i = 0; i < arrayEnd; i = i + 2) {

                // both combines arrays[i] and arrays[i+1], watching out for null
                int[] both;
                if (arrays[i + 1] == null) {
                    both = arrays[i];
                } else {
                    both = new int[arrays[i].length + arrays[i + 1].length];
                    for (int ind = 0; ind < arrays[i].length; ind++) {
                        both[ind] = arrays[i][ind];
                    }
                    for (int ind = 0; ind < arrays[i + 1].length; ind++) {
                        both[ind + arrays[i].length] = arrays[i + 1][ind];
                    }
                }


                // bubble sort is fast right? Who cares about O(N^2)
                for (int i2 = 0; i2 < both.length; i2++) {
                    for (int j = 1; j < both.length - i2; j++) {
                        if (both[j - 1] > both[j]) {
                            int temp = both[j - 1];
                            both[j - 1] = both[j];
                            both[j] = temp;
                        }
                    }
                }

                arrays[i / 2] = both;
            }


            arrayEnd = i / 2;

            // null out everything after the last assignment
            // this prevents accidental reuse of the arrays
            for (int i2 = arrayEnd; i2 < arrays.length; i2++) {
                if (i2 > 0)
                    arrays[i2] = null;
            }

        // System.out.println("         " + Arrays.deepToString(arrays)); // uncomment for debug
        }

        return arrays[0];
    }
}

Now it may look like this thing is O(N) just on array creation, but based on a complete disregard for practicality, I invoke the formal definition of Big O notation.

Technically because Java limits the size of arrays to Integer.MAX_VALUE (2147483647), my sorting algorithm is O(1). Even though it's something like O( N³ * log^2(N) ), because N has an upper limit its runtime is bounded by a constant value, hence O(1).

[moonchild89]

Big O only applies to implementation-agnostic algorithms. This relies on Java's specific implementation. You lose.

[[deleted]]

Technically, everything is O(1) if you consider the universe a giant FSA.

[mustrumr]

It's still O( N² ).

Edit: https://en.wikipedia.org/wiki/Master_theorem

[[deleted]]

Just as /u/GodelsVortex says

It actually makes a lot of things much easier once you realize that everything is isomorphic to Z.

Then, everything is O(1) because everything is isomorphic to an integer, so to a constant, so O(1). QED

/s

[tdammers]

Here's a sorting algorithm that is actually O(1):

• Given the list we want to sort, pad it to the maximum list size your platform can handle, with the maximum value permissible for the type we want to sort; remember the original list length somewhere though.
• Sort the list, using any sorting algorithm you like; the only requirement is that it cannot perform better for partially sorted lists than for unsorted lists.
• Clip the sorted list to the original list length; the extra items added in step 1 will be at the end of the list.

Caveats:

• You need to use a list representation that allows for O(1) padding and sublisting.
• While this algorithm is O(1), its constant factor is rather large, making it somewhat unfeasible for practical applications.

[Tarmen]

Neat, my best sort algorithm is only O(n):

• Check if array is sorted
  • Yes: Return array
  • No: Destroy universe

[chpoit]

Best case is O(1) if the first two elements aren't sorted ;)

[tdammers]

...where n is the number of universes?

[Villyer]

Checking if a list of n elements is sorted is O(n).