seek the fastest sorting algorithm for some arrays

Question

I have some short arrays that have been sorted. then I want to merge them into one large arrays and required to keep order. so how to implement that in fastest time and simplest complexity.

for example, I have three short array:

1 2 3 5 9
4 6 8 10 11
7 12 15 20 21

the merge result is: 1 2 3 4 5 6 7 8 9 10 11 12 15 20 21

of course, above example is so simple. In fact, my final result could be one millon integers together, may be some simple algorithm can be apply to work, such as bubble sort, quick sort, or heap sort etc, but I wanna the best effective algorithm to do it. can you give some resolution or good suggestion?

Thanks all for your answers below this question. I am just writing some routine for testing. I will use insert sorting algorithm and comparied to STL quick sort which is used in my older version project, so I want to see which's more fast?

In my opinion, insert sort will enhance the processing because of pre-sorting character of all the short arrays. I need to insert other short arrays into the first short array one by one. Another more helpful thing is that the first element of every other short arrays can tell you the base insert position after first vistor, so avoid to visit whole arry when deal with later element. Can you understand what I am talking? you guys, wait for my testing result. Thanks!

This sounds an awful lot like a homework question. Have you made any attempts? — Dylan Lawrence
– Dylan Lawrence, Commented Sep 5, 2014 at 2:55
You said you have 3 arrays, put I only see one, can you add some separators or smt to make it clearer? — Pham Trung
– Pham Trung, Commented Sep 5, 2014 at 2:57
@DylanLawrence I am just doing it. May be some suggestion will be appreciated, so I can improve my idea later — DarkHorse
– DarkHorse, Commented Sep 5, 2014 at 3:10
@DarkHorse Hmm, well the fastest sort is either going to be merge sort or 3-partition quicksort. You can get between O(n) and O(nlogn) if you use merge sort since some amount of this does contain natural variants. — Dylan Lawrence
– Dylan Lawrence, Commented Sep 5, 2014 at 3:14
Given the criteria I want to merge them into one large arrays I woul suggest merge sort. It is comparable to quick sort in efficiency and asymptotic behaviour, and wholly appropriate for this task. — Pieter Geerkens
– Pieter Geerkens, Commented Sep 5, 2014 at 3:15

Pham Trung · Accepted Answer · 2014-09-05 05:16:42Z

2

As all three arrays are sorted, we can have an simple algo which merge three arrays in O(n), with n is length of array. The idea is similar to merge part in merge sort.

Start from the beginning of each array, compare these elements together to find the minimum values in those 3 arrays. Add the minimum one into the result.
Increase the index from the array which the minimum element has been taken.
Repeat the process.

Java Code:

public int[] sort(int[][] data) {
    int n = 0;//Total length of all arrays
    for(int i = 0; i < data.length; i++){
        n += data[i].length;
    }
    int[] index = new int[data.length];//Array to hold the index of each arrays
    int []result = new int[n];
    for (int i = 0; i < n; i++) {
         int min = -1;
         for (int j = 0; j < data.length; j++) {//Find the smallest element in all arrays
              if (index[j] < data[j].length){
                  if(min == -1 || data[min][index[min]] > data[j][index[j]]){
                     min = j;
                  }                    
              }
         }
         result[i] = data[min][index[min]];
         index[min]++;
    }
    return result;
 }

Edit: if the number of array is varied , so the above algo is O(m*n) with m is number of array.

Another way to improve this algo is to introduce a min heap data - structure, which size of the heap is always <= m, and when there is an element pop out of the heap, one element from the same array will be fetched back into the heap, which made the time complexity of the algo is O(n log m)

edited Sep 5, 2014 at 5:16

answered Sep 5, 2014 at 3:29

Pham Trung

11.3k2 gold badges26 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

DarkHorse Over a year ago

Thanks! Good idea. I make testing to compare your method to quick sort used in STL algorithm, but wired thing happened. firstly I build up 16 short arrays and every array are filled with about 20,000 random integers, then every array was pre-sorted with basic algorithm such as bubble sort. After prepared work finished, I make two steps for testing. one is for stl algorithm, the other is for simple merge algorithm you have mentioned. each one step is to test running time three times. The developing environment is win7 and vs2010. In win32 debug mode, the result is:

DarkHorse Over a year ago

* stl: 541ms Mine: 32ms * stl: 615ms Mine: 30ms * stl: 568ms Mine: 32ms And then, I switch to win32 release mode, but opposite result occured: * stl: 41ms Mine: 162ms * stl: 41ms Mine: 227ms * stl: 36ms Mine: 173ms why this result is so different from that in debug mode? Should optimization from compiler could enhance STL library so brightly? if so, how to interpret the reason why the duration time of my algorithm becomes slower in release mode? This is the whole code I am running: click here

Collectives™ on Stack Overflow

seek the fastest sorting algorithm for some arrays

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related