Find the best sort algorithm

ndkit

Dear all, Currently, I'm finding the best sort algorithm for my case as below: I already have 3 input arrays that are increment sorted by times (each array contains about 1,000,000 elements). Now, I want to merge 3 arrays to one arrays (of course, it must be sorted). Pls. support me to find the best way to do it, to improve performance as much as posible. Thanks for your support!

Alex Manolescu

Hi, the best sorting algorithm for you're case is [Quicksort]. For you're 3 arrays: A, B and C, you can merge A with B into D, then sort D. Afther that, merge D with C into E, then sort E. The final result will be the E array. Cheer's, Alex Manolescu

ndkit

Thanks Alex, Can you explain more detail? Now, I'm undestanding: Quicksort is used for sorting D array after merge A & B. 1. If that's right, why don't we use merge sort to merge A&B to sorted D array? 2. If wrong, which algorithm you use when merge A&B?

dan sh

This[^] should help you choose one.

Alex Manolescu

Hi, the example that i provided you is just an example. You can find many ways to sort an array. For you're questions: 1. yes, you understand right! of course you can use merge sort if you wish, i've provided you just an example. (another example: you can use quicksort to sort array A and B, then apply quicksort on D array!) 2. you can loop trough array A and B to fill the D array. To see which algorithm is better try to set a timer at the start of the algorithm and at the end you'll see which is more faster :) Cheer's, Alex Manolescu

riced

Do you actually need to sort them? If the three arrays are already sorted and you just need to merge them then you could loop down them in parallel and copy the smallest value to the new array. You need to increment the index for the copied value only and then loop around again.

Regards David R --------------------------------------------------------------- "Every program eventually becomes rococo, and then rubble." - Alan Perlis

PIEBALDconsult

To find the best sort algorithm you must first get the value of each algorithm and then sort them... :-D

riced

Here's an implementation that does what I think you want. Note: it uses Lists instead of Arrays. If you must use arrays then the output array must be big enough to hold all three input arrays. Note: it relies on having a value (HIGH_VALUE) greater than any that can appear in any of the input arrays. I've not done an analysis but don't think you can do it quicker. This goes through each array (List) only once. Any other approach probably needs multiple passes through the arrays.

using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
class Program
{
static List<int> listA = new List<int>();
static List<int> listB = new List<int>();
static List<int> listC = new List<int>();
static List<int> listOut = new List<int>();

  static void Main(string\[\] args)
  {
     MakeSortedLists();   //with test data for lists A, B and C
     const int HIGH\_VALUE = int.MaxValue; //Dummy value greater than max in any list

     int m = 0;  // listOut index - only need this if listOut is really an array
     int i = 0;  // listA index
     int j = 0;  // listB index
     int k = 0;  // listC index

     int valueA = listA\[0\];
     int valueB = listB\[0\];
     int valueC = listC\[0\];

     while ((valueA < HIGH\_VALUE) || (valueB < HIGH\_VALUE) || (valueC < HIGH\_VALUE))
     {
        if ((valueA <= valueB) && (valueA <= valueC))
        {
           listOut.Add(listA\[i\]);       //listOut\[m\] = listA\[i\] IF listOut is an array
           i++;
           valueA = (i < listA.Count) ? listA\[i\] : HIGH\_VALUE;
        }
        else
        {
           if ((valueB <= valueA) && (valueB <= valueC))
           {
              listOut.Add(listB\[j\]);    //listOut\[m\] = listB\[j\] IF listOut is an array
              j++;
              valueB = (j < listB.Count) ? listB\[j\] : HIGH\_VALUE;
           }
           else
           {
              listOut.Add(listC\[k\]);    //listOut\[m\] = listC\[k\] IF listOut is an array
              k++;
              valueC = (k < listC.Count) ? listC\[k\] : HIGH\_VALUE;
           }
        }
        m++; // only need this if listOut is really an array
     }

     WriteOutList();
     Console.ReadLine();
  }

  static void MakeSortedLists()
  {
     li

ndkit

Thanks for your support.