The Stack Overflow podcast is back! Listen to an interview with our new CEO.
54

Don't do this using namespace std; This is a bad habit that will get you into a lot of trouble. Please break the habit before it becomes ingrained. see: Why is “using namespace std” considered bad practice? Note: The reason the "standard" library uses the namespace std:: is so that it is not a large burden to use as a prefix. Prefer '\n' over std::endl ...


45

Avoid std::endl At least at first glance, it looks like you've committed the single largest sin in C++ with respect to file I/O speed: you've used std::endl where all you really wanted was a new-line ('\n'). I haven't tested your specific code, but past experience indicates that just writing '\n' instead of endl to end a line, by itself, will improve your ...


30

Don't use using namespace std; in global scope, that's a bad habit to get into. If you really dislike writing std:: over and over again then put it in function scope where needed. But even then avoid importing whole namespaces and instead only import the specific identifiers. Indentation isn't consistent, this may be a copy-paste error but it is distracting. ...


15

Here are some things that may help you improve your code. Don't abuse using namespace std Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Use nullptr rather than NULL Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful. Use more whitespace Lines like this one: ...


14

A C++ merge sort in the style of a Standard Library algorithm could be written as template<class BiDirIt, class Compare = std::less<typename std::iterator_traits<BiDirIt>::value_type>> void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare()) { auto const N = std::distance(first, last); if (N < 2) return; ...


14

Binary operators should always be surrounded by whitespaces(it is inconsistent in your code: sometimes you do surround them, sometimes you don't). For example, for (int j=0; j<a.length; j++) should be for (int j = 0; j < a.length; j++) There should be one whitespace before an opening bracket. Again, there is an inconsistency in your code: a ...


14

Your temp array is static, this immediately makes your function not thread-safe and non-reentrant. Instead add it to the parameter list.


14

Your big mistake is not using iterators. As a result you pass your vectors by value, which causes the vectors to be copied a lot. std::vector<int> MergeSort(std::vector<int> arr) ^^^ A copy of the array is made when you call this function. std::vector<int> Merge(std::vector<int> arr1, ...


13

Just a few unsorted ideas: Mergesort can be very nicely expressed using Scala's streams. In particular: def merge(first: Stream[Int], second: Stream[Int]): Stream[Int] = (first, second) match { case (x #:: xs, ys@(y #:: _)) if x <= y => x #:: merge(xs, ys) case (xs, y #:: ys) => y #:: merge(xs, ys) case (xs, ...


13

Looks good. Couple of things I would do differently (not that your way is wrong). Rather than pass references to the containers around I would pass iterators into the containers. This allows your sort algorithm to be container agnostic: void merge_sort(std::vector<int>& numbers) {} // My version looks like this template<typename I> ...


13

Overall I would have to say that this is the neatest and most clear implementation of a Merge Sort that I have seen. There is nothing wrong with variables i, j and k. They are standard names for looped array indexes. There is a single empty line in your code which is inconsistent with the rest of the method. That is the only nitpick I can find in terms of ...


12

Generally, you should do what you can not to throw an exception - it is slow and it looks bad. In this case, you should go with: if (fstIndex<fst.length){ fstIndexValue = fst[fstIndex]; } else { System.arraycopy(snd, sndIndex, result, fstIndex + sndIndex, snd.length - sndIndex); break; } ...


12

Yes, it's a mergesort, switching to something else for small ranges is a common refinement. Be aware your implementation is not stable, though it doesn't matter for int on your machine. You can easily address that at no extra cost. Change: if (arr1[i1] < arr2[i2]) into if (arr1[i1] <= arr2[i2]) Use templates, for the inputs type and an optional ...


11

Overview Good first try. It seems like it works. But currently it only works for vectors and ints. Some thoughts for improving the algorithm in the future. If you look at most C++ algorithms they don't take a container as a parameter (vector<> is a container), instead they take iterators into the container. That way the algorithm can be used on any ...


11

#include<iostream> #include<vector> #include<random> #include<chrono> Leave some space between the #includes and the rest of your code, that's easier to read. Besides, I really like <chrono> myself too, but you don't seem to use it afterwards. using namespace std; using namespace std::chrono; using directives for a whole ...


10

As the others have pointed out, there is a lot of repetition in your code. This is however a great opportunity to threat the files as simple iterators from which you can extract integers. This is done using a simple C# generator. IEnumerator<int> ToIterator(StreamReader reader) { string line; while ((line = reader.ReadLine()) != null) { ...


10

Use your knowledge of the domain You may be able to compare numbers without parsing them, by working with strings instead. First compare the sign characters (if present), then skip leading zeros, then compare the length of the significant part, and only then perform a (string) comparison. You may be able to omit some of the above steps if you know that ...


10

Naming sub_merge is weird, as it doesn't match up at all with the meaning of the english word "submerge". I get its origin ("subroutine merge"), but why not simply call it merge instead? Algorithm This seems like a straightforward top-down implementation of mergesort. However, there are some issues: Stability sub_merge doesn't preserve the relative ...


9

I can't fault too much here, it's generally looking pretty reasonable. I think the first point below is the most important, depending on how much experience you have with C, the second may or may not make much sense. Information Hiding Firstly, you should split this up into separate .h and .c files; perhaps you've already done this but just pasted them ...


9

In merge(), you call malloc() twice with no corresponding calls to free(). That can't be good for your memory consumption! When computing the average of two values, don't do q = (p+r)/2, because that is vulnerable to overflow. Instead, write it as q = p + (r - p) / 2.


9

Well, interesting. There's a bug in merge_sort(): Subtracting 1 from end, without knowing whether the range is empty, is Undefined Behavior. Subtract the iterators and compare the difference instead. While you are at it, use std::distance for that. There's no need to move the second half out of the way in sub_merge(): You are merging from the front, and the ...


8

You currently have: i, j, k = 0, 0, 0 #i= left counter, j= right counter, k= master counter Don't write minified code. Use variable names. left_counter, right_counter, master_counter = 0, 0, 0


8

I could not work out how to merge without using a temporary There are two distinct flavours of merge. One is a generic merge of two totally unrelated ranges, which cannot possibly happen inplace, with the signature template <typename I> void merge(I first1, I last1, I first2, I last2, I target); The second one, actually employed in the merge sort, ...


8

A proper C++ implementation would be generic, i.e. a code that can merge any linked lists (of the same type). This could be implemented by taking iterators (and templating over iterator type). At the present, your code looks like C. Btw, you can simplify the body of merge somewhat as follows auto p=l1.start, q=l2.start; auto append = [&](auto x) { l3....


8

Note: I'm at least trying to avoid repeating @Edward's points, which I think are all quite good. It looks like while I was writing this @Loki wrote a few things that are a lot closer to what I said--sorry 'bout that, but I think I raise at least a couple of interesting new points as well. I'd change a few things here. First, instead of leaving node as ...


8

Avoid a copy by passing by const reference. [](RandomAccessIterator::value_type const& a, RandomAccessIterator::value_type const& b) { return a < b; } ^^^^^^ ^^^^^^ Don't need an if statatement here: if (itUpper == last) std::copy(itLower, first + m, itResult); else ...


8

std::ceil(static_cast<double>(size) / 2 is a very long (and unclear) way to say size - size/2. No naked loops please. Each loop represents an important algorithm, and deserves a name. For example, while (array1 != array1end) new_array[na_pos++] = *array1++; wants to be copy(new_array + na_pos, array1, array1_end);, and you may reuse it at least 2 ...


7

Pass your parameters by const reference to avoid a copy: std::vector<int> merge2Sorted(std::vector<int> const& left, std::vector<int> const& right) // ^^^^^^ ^^^^^^ You are not reservng enough result.reserve(std::max(left.size(),right.size())); The result size ...


7

Steve is absolutely right that adding a buffered layer between the Data input/output streams and the File input/output streams, will make things work a whole lot better. I would also suggest changing to use a try-with-resources system, which will also close, and otherwise manage the files in a better way: try (DataInputStream dis1 = new DataInputStream(new ...


7

Your four questions are good ones: Correctness - are there any bugs? I can't see any significant bugs. There are lesser potential bugs which relate to unexpected input (for example, null lists, or lists with null members (each of those will throw NullPointerExceptions) Correctness - I used the language correctly? For the most part, it is neat, and well ...


Only top voted, non community-wiki answers of a minimum length are eligible