31

There is an array related problem, the requirement is that time complexity is O(n) and space complexity is O(1).

If I use Arrays.sort(arr), and use a for loop to one pass loop, for example:

public static int hello(int[]A){
  Arrays.sort(A);
  for(int i=0;i<A.length;i++){
     ....................
  }
  return ....;

}

So the loop will cost O(n) time. My question is: will Arrays.sort() cost more time? If I use Arrays.sort(), will this time complexity still be O(n)? And will Arrays.sort() cost more space?

9
  • This doesn't specify the sorting algorithm used, so I don't see how it is answerable. Commented Mar 21, 2014 at 23:59
  • 2
    @RobertHarvey: Unless one assumes Arrays.sort() to employ some magic, I think the question about what minimum time complexity it has is quite answerable, isn't it? Commented Mar 22, 2014 at 0:01
  • 2
    It specifies Arrays.sort, so whichever algorithm that uses. It's hard to tell what language this is (guessing Java), but standard library sorts are almost always comparison sorts. Commented Mar 22, 2014 at 0:01
  • 1
    Despite all of the nattering in the answers section below, the answer to your actual question is yes: sorting will in the average case take longer than O(n). Commented Mar 22, 2014 at 0:18
  • 2
    Assuming you know enough about big-O complexity, you really should be asking "What's Arrays.sort's time and space complexity?", which is really a question which shows no research effort, as this is fairly well-documented. Commented Mar 22, 2014 at 0:28

7 Answers 7

45

I am assuming you are talking about Java here.

So the loop will cost O(n) time, my question is that will Arrays.sort() cost more time?

Yes, Arrays.sort(int[]) in all Java standard library implementations that I know, is an example of a comparison-based sort and thus must have worst-case complexity Ω(n log n). In particular, Oracle Java 7 uses a dual-pivot quicksort variant for the integer overloads, which actually has an Ω(n2) worst case.

and will Arrays.sort() cost more space?

In all likelihood it will use ω(1) space (which means another yes, the space usage is not O(1)). While it's not impossible to implement a comparison-based sort with only constant extra space, it's highly impractical.

That said, under certain conditions it is possible to sort specific types of data in linear time, see for example:

With a constant range of input integers (for example if abs(A[i]) <= C for some constant C), then counting sort and radix sort use indeed only O(n) time and O(1) space, so that might be useful.

14
  • According to the docs, theta(n log n) is incorrect for time and theta(1) is incorrect for space. my post has the information from the docs. Commented Mar 22, 2014 at 0:04
  • @theSilentOne I have no idea what you're talking about, but I don't think you know what Ω means
    – Niklas B.
    Commented Mar 22, 2014 at 0:06
  • It means a lower bound. n log n is not the lower bound, according to the docs. Commented Mar 22, 2014 at 0:06
  • 3
    Correct me if I'm wrong, but saying that the sort has a lower bound of constant space isn't particularly meaningful - that applies to every single algorithm. Commented Mar 22, 2014 at 0:14
  • 1
    We usually talk about worst case in theoretical CS, that’s out of the question. Big-O is useful to state upper bounds, and Omega is useful to state lower bounds, which is what I wanted to do here
    – Niklas B.
    Commented Jun 13, 2020 at 16:11
10

According to the java jvm 8 javadocs of Arrays.sort() method:

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

So it will increase your time complexity from O(n) to O(n log(n))

4

Arrays.sort(int[] a) in recent JDK is implemented with Dual-pivot Quicksort algorithm which has O(n log n) average complexity and is performed in-place (e.g. requires no extra space).

2
  • 1
    In fact it requires Ω(log n) extra space at the very least
    – Niklas B.
    Commented Mar 22, 2014 at 0:22
  • Oh, you probably mean the execution stack space. You're right then, but I guess the question was about the heap space.
    – apangin
    Commented Mar 22, 2014 at 0:42
4

Arrays.sort(int[])

As well as Arrays.sort(long[]), Arrays.sort(float[]) and Arrays.sort(double[])

Time complexity

Time complexity of Arrays.sort(int[]) depends on the version of Java.

O(n2) prior to Java 14

A pretty ordinary quicksort was used with time complexity ranging from O(n) (when the array is already sorted and we are only checking that it is) to O(n2) for certain inputs that cause extremely uneven distribution of elements into parts with an average complexity of O(n log(n)). You can find a detailed analysis here.

O(n log(n)) starting from Java 14

In Java 14 the implementation was improved to guarantee the worst-case time complexity of O(n log(n)). The function was changed to resort to heapsort if recursion becomes too deep:

if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
  heapSort(a, low, high);
  return;
}

which prevents the method from degrading to quadratic time complexity.

Glimpse into the future

There is an initiative to switch to radix sort for almost random big enough arrays thus reducing the time complexity to O(n) in the worst-case.

O(n) space

In all versions, the algorithm has space complexity ranging from O(1) (when the array is already sorted and we only to check that it is) to O(n) (when the array is highly structured (there is a small number of sorted subarrays inside the original array and we merge those subarrays)).

Here's where allocation happens in the worst case:

/*
 * Merge runs of highly structured array.
 */
if (count > 1) {
  int[] b; int offset = low;

  if (sorter == null || (b = (int[]) sorter.b) == null) {
    b = new int[size];
  } else {
    offset = sorter.offset;
  }
  mergeRuns(a, b, offset, 1, sorter != null, run, 0, count);
}
return true;

DualPivotQuicksort.java

While the question asks specifically about Arrays.sort(int[]) method I still decided to include answers for other data types since this is the first result when you look for Arrays.sort() time and space complexity in Google and it is not easy to find correct answers to this simple question in other places.

Arrays.sort(short[])

As well as Arrays.sort(char[]) and Arrays.sort(byte[])

O(n) time, O(1) space

Although the documentation says:

The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on all data sets, and is typically faster than traditional (one-pivot) Quicksort implementations.

This is not true at least starting from Java 7. Actually, an in-place counting sort used for big enough arrays, which has linear time complexity and constant space complexity:

private static void countingSort(short[] a, int low, int high) {
    int[] count = new int[NUM_SHORT_VALUES];

    /*
     * Compute a histogram with the number of each values.
     */
    for (int i = high; i > low; ++count[a[--i] & 0xFFFF]);

    /*
     * Place values on their final positions.
     */
    if (high - low > NUM_SHORT_VALUES) {
        for (int i = MAX_SHORT_INDEX; --i > Short.MAX_VALUE; ) {
            int value = i & 0xFFFF;

            for (low = high - count[value]; high > low;
                a[--high] = (short) value
            );
        }
    } else {
        for (int i = MAX_SHORT_INDEX; high > low; ) {
            while (count[--i & 0xFFFF] == 0);

            int value = i & 0xFFFF;
            int c = count[value];

            do {
                a[--high] = (short) value;
            } while (--c > 0);
        }
    }
}

Counting sort implementation

Arrays.sort(Object[])

Unlike other methods, this one is well-documented and the documentation here corresponds to reality.

O(n log(n)) time

Starting from Java 7

This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons.

https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])

Before Java 7

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance.

https://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(java.lang.Object[])

O(n) space

Starting from Java 7

Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.

https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(java.lang.Object[])

Before Java 7

The algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort to sort object references is a "modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist)." It is a reasonably fast stable sort that guarantees O(n log n) performance and requires O(n) extra space.

https://bugs.openjdk.org/browse/JDK-6804124

3

It is more than O(n) time and requires more than O(1) space.

Arrays.sort() utilizes a modified Timsort in 1.7 which is a relatively recently developed sorting algorithm and it offers sorting with complexity x where O(n)< x < O(nlgn) and space of O(n/2)

6
  • You haven't quite convinced me that my statements "make no sense at all" because I'm pretty sure they do, but your comments have encouraged me to review my asymptotic complexities again. Commented Mar 22, 2014 at 0:24
  • @NiklasB., I'll definitely give it to you that saying it was the "fastest sort" was incorrect. I recently read an article about it and it performed better in many circumstances than quicksort or mergesort thus, "fastest" seemed inapproriately appropriate. I believe that you probably have a better understanding of the topic of asymptotic complexities than myself but I know that my comments would make sense to any non-PhD software engineer and are correct according to what Java's docs say. Commented Mar 22, 2014 at 0:46
  • 1
    @theSilentOne Let's leave it at that pal, no hard feelings
    – Niklas B.
    Commented Mar 22, 2014 at 0:47
  • 1
    @NiklasB. Thank you sir. I removed my childish downvote as well sheepish grin Commented Mar 22, 2014 at 0:49
  • 1
    In Java, Arrays.sort(int[] a) standard implementation uses quicksort, not Timsort. Object-based searches in since it is stable. Refs: docs.oracle.com/javase/7/docs/api/java/util/… and docs.oracle.com/javase/7/docs/api/java/util/…. Stable sort implementation of Object arrays is mandatory in Java. Commented Jan 8, 2017 at 21:14
1

Since you're talking about it in Java Language, the time complexity will surely increase from O(n) to O(nlogn). That's because in Java 8, Arrays.sort() is implemented in Dual-pivot quicksort algorithm, not single pivot . So it requires extra time. And space complexity of O(1) is not possible , since it requires more space, I guess O(n/2).

0
import java.util.Arrays;
public class MyClass {
    
    
    static void hello(int ac[]){
        
    }
    
    public static void main(String args[]) {
  
      int ac[] ={1,4,2,3,5};
    
       int i=0;
       int temp=0;
       
       while(i!=5-1){
            if( ac[i]>ac[i+1]){
               temp= ac[i];
               ac[i]=ac[i+1];
               ac[i+1]=temp;
               i= -1;
           }
           
          i++;
       }
       
      System.out.println(Arrays.toString(ac));



    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.