0
$\begingroup$

I have come up with an sorting algorithm that looks like $O(n \log \log n)$. Could anyone help to find if it is already commonly known or worth anything?

The time complexity seems to be: $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + O(n)$, which would lead to: $O(n \log \log n)$.

This algorithm divides into $\sqrt{n}$ pieces in $O(n)$ while Merge Sort takes $O(1)$ and Quick Sort takes $O(n)$ to both divide into 2. This algorithm takes $O(\sqrt{n})$ to merge while Merge Sort takes $O(n)$ and Quick Sort takes $O(1)$.

Pseudocode for p_sort

percentile_sort(input_array):

  if size(input_array) <= 1 then
     return input_array
  else if size(input_array) <= 2 then
     if input_array[1] < input_array[0] then
        input_array[0], input_array[1] = input_array[1], input_array[0]

  min_value = min(input_array)  -- O(1)
  max_value = max(input_array)  -- O(1)

  if min_value == max_value then
     return input_array

  num_buckets = max(2, square_root(size(input_array)))  -- O(1)

  foreach value in input_array  -- loops n times, time complexity O(n)
     bucket_index = integer((value - min_value)/(max_value - min_value) * num_buckets)  -- O(1)
     append value to buckets[bucket_index]

  foreach bucket in buckets  -- loop square_root(n) times, time complexity T(square_root(n))
        call percentile_sort(bucket)  -- recursive call
        append return vector to sorted_buckets

  return sorted_buckets

Here is my implementation and more details.

https://github.com/tomkob9999/percentile_sort

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ Did you experimentally assess the runtime of your implementation on pseudo-random input? Result? $\endgroup$ Commented Sep 13, 2024 at 4:45
  • 9
    $\begingroup$ Not that it affects the result of the calculations, but min and max are both $O(n)$ operations, and calculating square_root(n) is at best $O(log(n))$. $\endgroup$ Commented Sep 13, 2024 at 8:01
  • 2
    $\begingroup$ Why do you think that computing min(input_array) of an array is O(1)? $\endgroup$ Commented Sep 13, 2024 at 13:37
  • 1
    $\begingroup$ The linked benchmarks are a bit suspicious. It shouldn't take too long to sort 5M integers. And running the sample python code myself with the test parameters (5,000,000 integers between 1 and 5,000,000) gives vastly different results, such that p_sort is ~ an order of magnitude slower than just calling list.sort(). Perhaps the quick sort you are comparing against is not very robust? It would also be good to see averaging over multiple runs to discount things like CPU cache affecting performance etc $\endgroup$ Commented Sep 13, 2024 at 19:19
  • 4
    $\begingroup$ FYI, this is a version the (at one time) well known Interpolation Sort. See the link for for the standard take on its performance characteristics. $\endgroup$ Commented Sep 14, 2024 at 17:12

3 Answers 3

Reset to default
12
$\begingroup$

Your running time analysis is incorrect. Consider the case where most or all inputs fall into a single bucket. Then the running time is much worse than you list.

Your analysis seems to assume that each bucket will contain $\sqrt{n}$ values. This is not correct. A bucket can end up containing $n/2$ values (for example).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ OK. But maybe big O calculation is not accurate. But based on tests, data that have more dupulicates are actually sorted faster in this algorithm because in the next round, the duplicates are converged into a narrower variation. I haven't tried for skewed data but I suspect the same result is the same. $\endgroup$ Commented Sep 12, 2024 at 21:50
  • $\begingroup$ Just FYI, I just tested with some skewed data using exponential and gamma distribution. The result was as expected. It was the same or faster than uniformly distributed data. $\endgroup$ Commented Sep 12, 2024 at 21:58
  • $\begingroup$ Also, I am aware quick sort is known to be $O(n \log n)$ due to its average, but the worst case scenario is $O(n^2)$. $\endgroup$ Commented Sep 12, 2024 at 22:03
  • $\begingroup$ Sorry, I meant kurtosis, not skewness. The high kurtosis data tests showed that the depth of recursion and the average input size were not adversely affected. $\endgroup$ Commented Sep 13, 2024 at 0:34
8
$\begingroup$

EDIT: A quick search through the literature didn't reveal an exact match, but there are recursive variants of bucket sort, most notably radix sort, which differs from the proposed algorithm in having fixed number of buckets and their boundaries at each recursion levels. Radix sort is known to have worst case complexity of $O(w n)$ (where $w$ is the maximum size of individual numbers in bits).

The analysis of the algorithm at hand is a bit vague, but incorrect for multiple possible interpretations.

Note that the proposed calculation actually describes the best-case scenario, i.e. that the input values are distributed evenly into individual buckets. This appears very unlikely.

Now, let's look at worst-case complexity of your algorithm: For a sufficiently quickly growing input sequence (I think $1^1, 2^2, 3^3, ... , n^n$ should do) you'll have at each recursion step a single element in the last bucket and all remaining elements in the first bucket. So in this case, your algorithm degrades into selection sort and its $O(n^2)$ complexity.

If you want to claim average-case complexity, the analysis needs to be more careful. In particular, you need specify the distribution of input sequences you average over - since your algorithm is sensitive to the particular values (and not the order they are in), there is no single "natural" distribution to consider and different choices of such distribution are likely to yield different average complexities.

For example I'd expect i.i.d. draws from a Pareto distribution with small shape to produce a lot of quickly growing sequences making the average case close to the worst case outlined above. Draws from a uniform distribution OTOH are likely to have average complexity close to the best-case scenario.

EDIT: Mahmoud et al. 2000: Analytic variations on bucket selection and sorting provide a framework for analyzing the average-time complexity of multiple variants of bucket sort, and from a quick skim it seems their results shouldn't be too hard to adapt to the case at hand (they explicitly mention handling different number of buckets at each recursion level). It however also shows the level of technical detail that needs to be handled to provide a solid theoretical analysis.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you. I agree that the amortized time complexity analysis remains to be done more. But based on my repeated tests with more than a billion data with various distributed data (integers with duplicates, floats with uniform, normal, exponential, gamma including highly skewed and peaking ones), the number of recursions goes up to maximum of 7 while quick sort goes up to over 40. In each recursion level, the combined number of elements to be processed is the same (original n), so the number of recursion is the accurate measure. The algorithm corrects skeweness by itself as it moves down. $\endgroup$ Commented Sep 13, 2024 at 21:03
  • $\begingroup$ Regarding Pareto, I have not tested with Pareto, but I imagine it could cause worst case. One approach is to treat it as an edge case and detect if the distribution is in Pareto, and if yes, it redirects to another algorithm. Pareto detection seems like a O(1) task: for example, randomly pick 10,000 or 100,000 recs. Divide into 10 between min and max and check if one segment occupies 90%. Then recurse over this segment over 3 times or more. If it goes all the way, it can be considered to follow as a Pareto. $\endgroup$ Commented Sep 14, 2024 at 3:19
  • $\begingroup$ To handle exponential increase or decrease curve like Pareto, I also think they can be preprocessed to linearer shape by logging They can be either converted back by exponenting to closest value or keep index during sorting and replace back. They are both O(n) processes and don’t add up to the time complexity. $\endgroup$ Commented Sep 14, 2024 at 14:27
  • $\begingroup$ @TigerTora it turns out that assuming uniform distribution is quite common when analyzing non-comparative sorting aglorithms, so it probably is a bit more justifiable than I thought. I added a literature reference and some extra context. Please not that "amortized complexity" is a different thing than "average-case complexity" $\endgroup$ Commented Sep 15, 2024 at 9:31
  • 2
    $\begingroup$ @TigerTora I also think you need to choose your playground - if you want to do a "classical" CS algorithm complexity analysis, you need actual proofs, simulation results are not enough. If you want to show the algorithm has practical merit, you need to empircally measure its wall clock time. Mixing those approaches (like investigating recursion depth/no of steps in simulations) is IMHO useful only to let you better understand what's happening or to prevent you from wasting time proving a theoretical result that is contradicted by the empirical data, but are of little use by themselves. $\endgroup$ Commented Sep 15, 2024 at 9:31
1
$\begingroup$

This analysis appears to be potentially valid to me.

This algorithm would not be constrained by the proven $O(n \log n)$ lower bound on comparison sort average runtime is because it is not actually a pure comparison sort, it is in fact a hybrid comparison/bucket sort. In particular, the operation bucket_index = integer((value - min_value)/(max_value - min_value) * num_buckets) is a bucketing operation that relies on properties of the input data beyond what is required in a comparison sort, specifically that arithmetic operations can be performed on list elements and that they can be converted to integers. The average time complexity of bucket sort is around $O(n)$ when the number of buckets is close to the size of the input array, so it seems reasonable for a hybrid approach to have a time complexity between $O(n)$ and $O(n \log n)$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I'll admit I'm not 100% sure of that part, but the operation is concatenating together $O(\sqrt{n})$ subarrays so it seems reasonable to me that the runtime is $O(\sqrt{n})$. However, even if it's actually as slow as $O(n)$, that wouldn't change the overall conclusion, because it would just be one in a sequence of several $O(n)$ steps. If it is even slower than that, that would impact the runtime. Also, $\sqrt{n}$ is $n^{1/2}$; $n^{-2}$ is $1/n^2$. $\endgroup$ Commented Sep 13, 2024 at 15:09
  • 1
    $\begingroup$ I think this is insightful, but strictly speaking incorrect. The average case will depend on the choice of the distribution of input sequences - as I outline in my answer there is IMHO no single "natural" distribution and you can definitely construct distributions with bad average runtimes. $\endgroup$ Commented Sep 13, 2024 at 15:36
  • 1
    $\begingroup$ "you can construct distributions with bad average runtimes" that looks like worst case analysis to me. The analysis of bucket sort's average case runtime assumes a uniformly distributed input, so I don't think it's unreasonable to do the same thing here. $\endgroup$ Commented Sep 13, 2024 at 16:25
  • $\begingroup$ I just think you should explicitly mention somewhere that the results you discuss assume uniform distribution of input values and then we are in perfect agreement. $\endgroup$ Commented Sep 15, 2024 at 9:34

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.