1

I'm wondering which approach is the best with writing sorting algorithms, which sort-in-place (does not require additional space and sort an array it is given without copying it). Such examples are Insertion Sort, Quick Sort and others.

So far most of the examples I encounter in github are following:

//...
public function sort(array $array): array
{
    //...

    return $array;
}

Isn't it not the most efficient way of writing this down in php? What I mean is that it loses completely all the 'in-place' benefits. It copies the array each time it is passed to the function and returns yet again a copied array.

Wouldn't it be better to use

//...
public function sort(array &$array): void
{
    //...
}

approach? So that we don't have any unnecessary copying and really sort things in-place. If we check memory_get_peak_usage() values it shows that the latter (with the reference &) is almost twice lower than the first method.

I know references are not really 'best practice' in many cases and frowned upon, but here it seems they do really have their fair place, don't they?

hvertous
  • 1,133
  • 11
  • 25
  • Uhm, sure…? The built-in sort functions all work with references, so yours can too. – deceze Jan 11 '19 at 15:05
  • most examples I see in GitHub do not use references – hvertous Jan 11 '19 at 15:11
  • 2
    ‍♂️ Statistically speaking, most PHP code is terrible, so that's an unreliable metric. – deceze Jan 11 '19 at 15:24
  • Quicksort needs O(log(n)) stack space for recursion, assuming after doing a partition step, it uses recursion for the smaller part and iteration for the larger part, else worst case is O(n) stack space. Not mentioned in the wiki article are variations of in place merge sort. [block merge sort](https://github.com/Mrrl/GrailSort/blob/master/GrailSort.h) is in place, stable, and about 50% slower (takes 1.5 times as long) as a standard merge sort. – rcgldr Jan 12 '19 at 16:02

0 Answers0