Geek Answers Handbook

Why does the Sun Arrays.sort implementation create a clone of the input array?

Can someone explain the following code?

Source: Arrays.class,

public static <T> void sort(T[] a, Comparator<? super T> c) { T[] aux = (T[])a.clone(); if (c==null) mergeSort(aux, a, 0, a.length, 0); else mergeSort(aux, a, 0, a.length, 0, c); }
  • Why create aux?
  • How does this type ever work if code sorts aux?
  • Isn't it a waste of resources to clone an array before sorting?
+4
source share
3 answers

1: Why create aux?

Because the mergeSort method requires a source and target array.

2: How does this type work if the code sorts aux?

Since the mergeSort method mergeSort sorted from aux to a

3: Isn't it a waste of resources to clone an array before sorting?

No, this is not ... using this implementation of mergeSort . Now, if sort returned a sorted array, doing cloning (rather than creating an empty array) would be wasteful. But the API requires it to do the sorting in place, which means that a must be a "destination". Thus, elements must be copied to a temporary array, which will be the "source".

If you look at the mergeSort method, you will see that it recursively splits the array to be sorted, combining back and forth between its source and target arrays. For this you need two arrays. Presumably, Sun / Oracle has determined that this algorithm provides good performance for typical use cases of Java sorting.

+2
source

Read the mergeSort source .

This is a non-inplace sort with two parameters ( src and dest ).
It sorts the dest parameter and uses the src parameter for reference.

+2
source

Scroll down in this source file and see how the recursive mergeSort works. I think this is too complicated to try to explain in the post here, so here is a good link:

http://en.wikipedia.org/wiki/Merge_sort

0
source

More articles:


All Articles