0

I have an information that the method sorted() in Stream API maybe to use merging sort (mergesort).

Then time complexity for the kind of sort :

Big Θ (n (log n) ) - best

Big Ω (n (log n) ) - average

Big O (n (log n) ) - worst

space complecity – O (n) - worst

And what is the time complexity if we use sorting by multiple fields of a custom object, using then.comparing() to build a chain of comparisons ?

How would you calculate the time complexity in such a case ?

skyho
  • 1,438
  • 2
  • 20
  • 47
  • That depends on the functions you pass to the comparator factory. Normally, it does not affect the time complexity at all. – Holger Apr 20 '21 at 07:22
  • Normally compare function complexity is constant. So time complexity would be the number of compare * compare function complexity. – Eklavya Apr 20 '21 at 07:43
  • @Eklavya, @ Holger: so the time complexity remains - n (log n) and it doesn't depend from comparator functions? – skyho Apr 20 '21 at 09:21
  • 1
    @skyho if your compare function complexity remains constant then obviously. But if compare function complexity is like O(n) then sorting complexity will be n* n (log n) – Eklavya Apr 20 '21 at 09:23
  • 1
    Time complexity as a function of *n* depends on the chosen *n* and in turn, on the function’s dependency on *n*. Normally, for sort algorithms, *n* corresponds to the size of the list or array to sort. Then, typical comparison functions do not depend on *n*, hence, have a time complexity of O(1). This implies that the general time complexity of the particular sort algorithm remains, like O(n log n), regardless of the comparator function. An example for a different metric is evaluating the time complexity of sorting a list of very large strings, i.e. *n* strings of *m* characters on average. – Holger Apr 20 '21 at 09:53

1 Answers1

1

While the actual algorithm used in Stream.sorted is intentionally unspecified, there are obvious reasons not to implement another sorting algorithm, but use the existing implementation of Arrays.sort.

The current implementation uses TimSort, a variation of merge sort that can exploit ranges of pre-sorted elements within the input, with a best case of being entirely linear, when the input is already sorted, which also applies to the possible case that the input is sorted backwards. In these cases, no additional memory is needed. The average case is somewhere between that best case and the unchanged worst case of O(n log n).

As explained in this answer, general statements about the algorithms used in Arrays.sort are tricky, because all of them are hybrid sort algorithms and constantly improved.

Normally, a comparison function does not depend on the size of the input (the array or collection to sort), which doesn’t change when using Comparator.comparing(…).thenComparing(…), as more expensive comparison functions only add a constant factor that doesn’t affect the overall time complexity, as long as the comparator still doesn’t depend on the input size.

Holger
  • 285,553
  • 42
  • 434
  • 765