We changed our privacy policy. Read more.
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. ...


17

Merge is usually O(m) time, where m is the number of elements involved in the merge. Due to your insertions and deletions, it's rather O(mn), where n is the length of the entire list. That makes your whole sort O(n^2 log n) time instead of mergesort's usual O(n log n). You call it inplace sort, which suggests it doesn't return anything, but you do return the ...


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.


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 ...


13

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 ...


13

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, ...


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; } ...


11

First of all, there is a bug in the code - if an array is empty, you'll get a "maximum recursion depth exceeded" error. Improve your base case handling: if len(array) <= 1: return array Other improvements: the merging logic can be simplified - loop while where are elements in both arrays and append what is left after the loop extract the merging ...


11

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

#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 ...


11

Avoid code duplication Your code is more verbose than necessary, because you are repeating a lot of things unnecessarily, or write things in a more complex way than necessary. For example: (index + (index + length)) / 2 This looks really weird, and is actually equivalent to: index + length / 2 Which makes much more sense. Even with that change, that ...


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 the ...


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

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 ...


9

Welcome to Code Review! PEP-8 Python has a style guide to help developers write clean, maintainable and readable code. It is referred to as PEP-8. A few points of note: Avoid extraneous whitespace in the following situations: Use 4 spaces per indentation level. Type hinting Yet another PEP (PEP-484) for putting in type hints for your variables and function ...


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

Disclaimer: I'm also new to Rust, but I have a background in C, C++ and Haskell. Take everything I say with a grain of salt. All of that looks reasonable, except for the while loop and the ownership. And there's a bug. Bug on sorted vectors Did you try your code on sorted sets? #[test] fn it_works_on_sorted() { assert_eq!(merge_sort(vec![1, 2, 3, 4]),...


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 ...


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