CODEWITHSUNDEEP
arraysalgorithmsortingdata-structures
Pixel
Pixel

Reputation: 439

Sorting and merging two arrays in efficient way?

We have two arrays (not sorted), of capacity n and n+m. The first array has n elements. The second array has m elements (and additionally n places reserved for more elements).

The goal is to merge the two arrays and store the result in the second array in a sorted manner, without using extra space.

Currently, I sort both arrays using quick-sort and then merge them using merge-sort. Is there a more efficient way to achieve this???

Upvotes: 1

Views: 2611

Answers (5)

Rafael Baptista
Rafael Baptista

Reputation: 11499

Clearly the best thing to do is to copy the contents of N into the free space in the N+M array and quicksort the N+M array.

By doing 2 quicksorts and then a merge sort you are just making the entire operation less efficient.

Here is a mental exercise, if you had to sort an array of length M, would you split it into 2 arrays, M1 and M2, sort each and then merge sort them together? No. If you did that you would just be limiting information available to each call of quicksort, slowing down the process.

So why would you keep your two starting arrays separate?

Upvotes: 2

pjs
pjs

Reputation: 19853

Let's call the smaller array the N array and the other one the M array. I'm assuming the elements of the M array are initially in locations 0 through m-1. Sort both arrays using your favorite technique, which may depend on other criteria such as stability or limiting worst-case behavior.

if min(N) > max(M)
   copy N's elements over starting at location m [O(n) time]   
else
   move M's elements to the end of the M array (last down to first) [O(m) time]   
   if min(M) > max(N)
      copy N's elements over starting at location 0 [O(n) time for the copy]
   else
      perform classic merge: min of remaining m's and n's gets migrated
      to next available space in M [O(min(m,n) time]

Overall this is dominated by the initial sorting time, the merge phase is all linear. Migrating the m's to the end of the M array guarantees no space collisions, so you don't need extra side storage as per your specification.

Upvotes: 0

cahen
cahen

Reputation: 16636

If you are storing in a second array, than you are using extra space, but you can minimize that by helping the GC like this:

  • join both arrays in a second array
  • set both previous variables to null so they are eligible to be garbage collected
  • sort the second array, Arrays.sort(...) - O(n log(n))

Look at the javadoc for this method:

/**
  * Sorts the specified array into ascending numerical order.
  *
  * <p>Implementation note: 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.
  *
  * @param a the array to be sorted
  */
  public static void sort(int[] a) {

Upvotes: 0

malejpavouk
malejpavouk

Reputation: 4445

If i wanted to guarantee also the O(n*log(n)) behaviour, I would use modified version of Heapsort, which would use the both arrays as a base for the the heap, and would store the sorted data in the additional part of the array.

This also might be faster than two Quicksorts, because it does not require the additional merge operation. Also Quicksort is terribly slow, when small arrays are being sorted (the size of the problem is not mentioned the the setting of the problem).

Upvotes: 0

William Falcon
William Falcon

Reputation: 9813

You can explore merge sort.

https://www.google.com/search?q=mergesort&ie=UTF-8&oe=UTF-8&hl=en&client=safari#itp=open0

Or depending on the size, you can do quicksort on each array, and then merge them using the merge sort technique (or merge, then quicksort).

I would go with mergesort, it basically works by sorting each array individually, then it puts them together in order

You're looking at O(nlogn) for mergesort and O(nlogn) for quicksort, but possible O(n^2) worst case with quicksort.

Upvotes: 2

Related Questions