Home c++ C++ Merge Sort

C++ Merge Sort

Author

Date

Category


Answer 1, authority 100%

Another example is an iterative algorithm (aka bottom-up (bottom-up ) merge sort).

For a change, it is implemented in C in template-style (but g ++ recognizes the code as “its”). Those. the programmer sets the data type (and, if required, the comparison function), and the preprocessor generates code for the given data type.

Perhaps, for a start, it is worth giving a simple example of the implementation of this algorithm for an array of int:

void
merge (int a [], int t [], int i, int l, int n)
{
 int j = i + l, n1 = min (j, n), n2 = min (j + l, n), k = i;
 while (i & lt; n1 & amp; & amp; j & lt; n2)
  t [k ++] = a [i] & lt; = a [j]? a [i ++]: a [j ++];
 while (i & lt; n1)
  t [k ++] = a [i ++];
 while (j & lt; n2)
  t [k ++] = a [j ++];
}
void
umsort (int a [], int n)
{
 int * t = (int *) malloc (n * sizeof (int));
 int l = 1, i;
 while (l & lt; n) {
  for (i = 0; i & lt; n; i + = 2 * l)
   merge (a, t, i, l, n);
  l * = 2;
  for (i = 0; i & lt; n; i + = 2 * l)
   merge (t, a, i, l, n);
  l * = 2;
 }
 free (t);
}

and only then show it in generalized form.

// upmergesort_tmpl.h - bottom-up merge sort in C at template style
#ifndef SORT_NAME
#error "Must declare SORT_NAME"
#endif
#ifndef SORT_TYPE
#error "Must declare SORT_TYPE"
#endif
#ifndef SORT_CMP
#define SORT_CMP (x, y) ((x) & lt; (y)? -1: ((x) == (y)? 0: 1))
#endif
#define SORT_CONCAT (x, y) x ## _ ## y
#define SORT_MAKE_STR1 (x, y) SORT_CONCAT (x, y)
#define SORT_MAKE_STR (x) SORT_MAKE_STR1 (SORT_NAME, x)
// makes a function name like int_mergesort (),
// by which to call sorting
#define MERGE_SORT SORT_MAKE_STR (mergesort)
#define MERGE SORT_MAKE_STR (merge)
#ifdef __cplusplus
extern "C" {
#endif
void MERGE_SORT (SORT_TYPE * dst, const size_t size);
#ifdef __cplusplus
};
#endif
#ifndef SORT_NOCODE_GEN
#ifndef MIN
#define MIN (x, y) ((x) & lt; (y)? (x): (y))
#endif
/ *
 Merge 2 consecutively located in a [],
 starting at index start of already ordered arrays, size of elements.
 The result is placed in tmp [] (also from the start index)
 n - the size of the entire array to be sorted a []
 * /
static void
MERGE (SORT_TYPE a [], SORT_TYPE tmp [], size_t first, size_t size, size_t n)
{
 size_t second = first + size, // beginning of the second array
  end1 = MIN (second, n), // end of the first array
                 // (the point is that there may not be a second one ...)
  end2 = MIN (second + size, n), // end of the second array
  i = first; // index for the current element of the result in tmp []
 while (first & lt; end1 & amp; & amp; second & lt; end2)
  tmp [i ++] = SORT_CMP (a [first], a [second]) & lt; = 0? a [first ++]: a [second ++];
 while (first & lt; end1) // there are elements of the first
  tmp [i ++] = a [first ++];
 while (second & lt; end2) // or second
  tmp [i ++] = a [second ++];
}
void
MERGE_SORT (SORT_TYPE * dst, const size_t n)
{
 SORT_TYPE * tmp = (typeof (tmp)) malloc (n * sizeof (* tmp));
 size_t l = 1, // size of already ordered subarrays
  i; // index of a pair of consecutive merging subarrays
 // start merging with sequential subarrays
 // from one element
 while (l & lt; n) {
  for (i = 0; i & lt; n; i + = 2 * l)
   MERGE (dst, tmp, i, l, n);
  // the now sorted subarrays are twice as long, but they are in tmp []
  l * = 2;
  for (i = 0; i & lt; n; i + = 2 * l)
MERGE (tmp, dst, i, l, n);
  // and here their size doubled again and they are already in the right place (in a [])
  l * = 2;
 }
 free (tmp);
}
#endif // SORT_NOCODE_GEN
#undef SORT_CONCAT
#undef SORT_MAKE_STR1
#undef SORT_MAKE_STR

Now, how to use it.

Suppose we want to sort the command line arguments, treating them as integers and as double numbers.

For more interest, let’s make a separate file (compilation unit) with the double sorting function and the real_1000 () function, which makes an array of integer doubles reduced by 1000 times (well, at least something what to think of?).

The code for sorting integers (and for the sake of completeness (or to completely obscure the reader’s brain?)) and the code for sorting C lines we will generate right in main.

Then we get t.c:

# include & lt; stdlib.h & gt;
#define SORT_TYPE double
#define SORT_NAME real
#include "upmergesort_tmpl.h"
// here generated code for void real_mergesort (double *, size_t);
#ifdef __cplusplus
extern "C" {
#endif
 // even if we compile g ++, we will leave the name according to the rules of C,
 // since in main we assume this is C code ...
 double * real_1000 (int *, int);
#ifdef __cplusplus
};
#endif
double * real_1000 (int a [], int n) {
 double * d = (typeof (d)) malloc (sizeof (* d) * n);
 int i;
 for (i = 0; i & lt; n; i ++)
  d [i] = a [i], d [i] / = 1000;
 return d;
}

AND main (in the upm_t.c file)

# include & lt; stdio.h & gt;
#include & lt; stdlib.h & gt;
#include & lt; string.h & gt;
#define SORT_TYPE int
#define SORT_NAME int
#include "upmergesort_tmpl.h"
// generated the code int_mergesort (int *, size_t);
#undef SORT_TYPE
#undef SORT_NAME
#undef SORT_CMP
#define SORT_TYPE char *
#define SORT_NAME str
#define SORT_CMP strcmp
#include "upmergesort_tmpl.h"
// generated code str_mergesort (char *, size_t)
// and set strcmp () to compare items
#undef SORT_TYPE
#undef SORT_NAME
#undef SORT_CMP
#define SORT_TYPE double
#define SORT_NAME real
#define SORT_NOCODE_GEN
#include "upmergesort_tmpl.h"
// generated prototype real_mergesort (double *, size_t) for the compiler
#ifdef __cplusplus
extern "C" {
#endif
 // assume she might be. compiled gcc -c
 double * real_1000 (int *, int);
#ifdef __cplusplus
};
#endif
int
main (int ac, char * av [])
{
 int a [ac], n = ac - 1, i;
 for (i = 1; i & lt; ac; i ++)
  a [i - 1] = atoi (av [i]);
 int_mergesort (a, n);
 for (i = 0; i & lt; n; i ++)
  printf ("% d \ n", a [i]);
 puts ("--- sort all argv [] ---");
 str_mergesort (av, ac);
 for (i = 0; i & lt; ac; i ++)
  printf ("% s \ n", av [i]);
 puts ("-----");
 double * d = real_1000 (a, n);
 real_mergesort (d, n);
 for (i = 0; i & lt; n; i ++)
  printf ("% f \ n", d [i]);
 free (d);
 return puts ("End") == EOF;
}

The result will be something like:

avp @ avp-xub11: hashcode $ g ++ -c t1.c
avp @ avp-xub11: hashcode $ g ++ upm_t.c t1.o
avp @ avp-xub11: hashcode $ ./a.out 1 2 3 iii ./bb aaa -2 -7
-7
-2
0
0
0
1
2
3
--- sort all argv [] ---
-2
-7
./a.out
./bb
1
2
3
aaa
iii
-----
-0.007000
-0.002000
0.000000
0.000000
0.000000
0.001000
0.002000
0.003000
End
avp @ avp-xub11: hashcode $

Everything is OK with gcc.


Answer 2, authority 100%

Merge Sort is a stable sort that runs in O (n log n) and uses O (n) extra memory.

C++ already has a standard algorithm std :: inplace_merge , which concatenates two sorted parts of the same sequence. With this algorithm, top-down merge sort can be written as follows:

template & lt; typename BidirIterator, typename Compare = std :: less & lt; & gt; & gt;
void merge_sort (BidirIterator first, BidirIterator last, Compare cmp = {}) {
  auto n = std :: distance (first, last);
  if (n & lt; 2) return; // Nothing to sort.
  auto middle = std :: next (first, n / 2);
  merge_sort (first, middle, cmp);
  merge_sort (middle, last, cmp);
  std :: inplace_merge (first, middle, last, cmp);
}

Answer 3, authority 57%

# include & lt; vector & gt;
template & lt; typename T & gt;
inline void swap (T & amp; arg1, T & amp; arg2)
{
  T temp = arg1;
  arg1 = arg2;
  arg2 = temp;
};
template & lt; typename T & gt;
inline void merge (std :: vector & lt; T & gt; & amp; vArray, std :: vector & lt; T & gt; & amp; vTemp, int head, int middle, int tail)
{
  int tmp = 0, lower = head, upper = middle + 1;
  while (lower & lt; = middle & amp; & amp; upper & lt; = tail)
  {
    if (vArray [lower] & lt; vArray [upper])
    {vTemp [tmp ++] = vArray [lower ++]; }
    else
    {vTemp [tmp ++] = vArray [upper ++]; }
  }
  if (lower & lt; = middle)
  {
    for (; lower & lt; = middle; vTemp [tmp ++] = vArray [lower ++]);
  }
  else
  {
    for (; upper & lt; = tail; vTemp [tmp ++] = vArray [upper ++]);
  }
  int arrayPointer = head;
  for (tmp = 0; arrayPointer & lt; = tail; vArray [arrayPointer ++] = vTemp [tmp ++]);
}
template & lt; typename T & gt;
inline void merge_sort_helper (std :: vector & lt; T & gt; & amp; vArray, std :: vector & lt; T & gt; & amp; vTemp, int head, int tail)
{
  if (head == tail)
  {return; }
  int middle = (head + tail) / 2;
  merge_sort_helper (vArray, vTemp, head, middle);
  merge_sort_helper (vArray, vTemp, middle + 1, tail);
  merge (vArray, vTemp, head, middle, tail);
}
template & lt; typename T & gt;
void merge_sort (std :: vector & lt; T & gt; & amp; vArray)
{
  std :: vector & lt; T & gt; v (vArray.size (), 0);
  merge_sort_helper (vArray, v, 0, vArray.size () - 1);
}

Programmers, Start Your Engines!

Why spend time searching for the correct question and then entering your answer when you can find it in a second? That's what CompuTicket is all about! Here you'll find thousands of questions and answers from hundreds of computer languages.

Recent questions