NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
merge_sort.h
Go to the documentation of this file.
1 /*
2  * nvbio
3  * Copyright (c) 2011-2014, NVIDIA CORPORATION. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  * * Redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer.
9  * * Redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution.
12  * * Neither the name of the NVIDIA CORPORATION nor the
13  * names of its contributors may be used to endorse or promote products
14  * derived from this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19  * DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY
20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  */
27 
28 #pragma once
29 
30 #include <nvbio/basic/types.h>
31 #include <iterator>
32 
33 namespace nvbio {
34 
35 namespace mergesort {
36 
46 template <typename Iterator, typename Compare>
48 void merge(Iterator A, uint32 int_left, uint32 int_right, uint32 int_end, Iterator B, const Compare cmp)
49 {
50  uint32 i0 = int_left;
51  uint32 i1 = int_right;
52 
53  // while there are elements in the left or right lists
54  for (uint32 j = int_left; j < int_end; ++j)
55  {
56  // if left list head exists and is <= existing right list head
57  if (i0 < int_right && (i1 >= int_end || (!(cmp( A[i1], A[i0] )))))
58  {
59  B[j] = A[i0];
60  i0 = i0 + 1;
61  }
62  else
63  {
64  B[j] = A[i1];
65  i1 = i1 + 1;
66  }
67  }
68 }
69 
70 } // namespace merge_sort
71 
81 template <typename Iterator, typename Compare>
83 bool merge_sort(uint32 n, Iterator A, Iterator B, const Compare cmp)
84 {
85  if (n == 1)
86  return false;
87 
88  // each 1-element run in A is already "sorted":
89  // make successively longer sorted runs of length 2, 4, 8, 16...
90  // until whole array is sorted
91 
92  // sort pairs in place to avoid unnecessary memory traffic
93  const uint32 nn = (n & 1) ? n-1 : n;
94  for (uint32 i = 0; i < nn; i += 2u)
95  {
96  if (cmp( A[i+1], A[i] ))
97  {
98  typename std::iterator_traits<Iterator>::value_type tmp = A[i];
99  A[i] = A[i+1];
100  A[i+1] = tmp;
101  }
102  }
103 
104  // merge longer and longer runs in a loop
105  bool swap = 0;
106  for (uint32 width = 2u; width < n; width *= 2u, swap = !swap)
107  {
108  // array A is full of runs of length width
109  for (uint32 i = 0; i < n; i += 2u * width)
110  {
111  // merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
112  // or copy A[i:n-1] to B[] ( if(i+width >= n) )
113  mergesort::merge( A, i, nvbio::min(i+width, n), nvbio::min(i+2*width, n), B, cmp );
114  }
115 
116  // now work array B is full of runs of length 2*width, swap A and B.
117  Iterator tmp = A;
118  A = B;
119  B = tmp;
120  }
121  return swap;
122 }
123 
124 } // namespace nvbio