If you are at a recursive call for the range [left, right], then place the first half of this range into temporary storage, and store the merge results in this range directly. For example, if our [left, right] range contained: [left, right] = 1 4 8 2 5 9 We...

c++,sorting,iteration,mergesort

I've finally figured it out. In pseudocode: for( outer = 1, outer < length, outer *=2) for(inner = 0; inner < length, inner = inner + (outer *2)) left = inner middle = (inner + outer) - 1 right = (inner + (outer * 2)) - 1 merge(items, left, middle,...

The problem is, that the borders of the array are inclusive which means: When you access the positions from 6-8 there are 3 elements in your result (6,7,8). The logical result is: If you want just one element described by a range in an array you would have to write...

java,algorithm,sorting,mergesort

The problem is because you are cloning the array and each time you call the mergeSort() function, it again clones the array. It needs to be cloned only the first time function is called. Here is the complete solution for your problem. You should call the first mergeSort() function. public...

performance,algorithm,mergesort

Let the array be of size N. Basically take the array and divide into two parts form 1 to N/2 and N/2 + 1 to N. Let us call these parts L and R respectively. Now if we can sort L and R separately we can just merge them to...

c,algorithm,data-structures,mergesort,doubly-linked-list

A bottom up merge sort is more appropriate for sorting a linked list. An efficient method for doing this is to use an array of pointers to the first nodes of lists, where the number of nodes pointed to by array[i] is 2^i (2 to the power i), or array[i]...

java,android,sorting,quicksort,mergesort

The key issue is sort stability - if two elements are equal from the point of view of the sort order, do they appear in the result in the same order as in the input. It does not matter for e.g. long. All instances of 3 in the input will...

performance,c++11,mergesort,chrono,ctime

No way two time measurements took 20 seconds. As others pointed out, results would be really dependent on platform, compiler optimization (debug mode can be really slower than release mode) and so on. If you have the same setting as your friends and still have performance issue, you may want...

c++,algorithm,sorting,mergesort,insertion-sort

There are two issues in your sort() routine - you're only sorting from mid to high (instead of low to high), leaving things half-unsorted. Once that's fixed, you need to stop j when it moves below low, not 0, since we're not always working from the start of the array....

At the point where you merge l and r back in to nums, have l and r been sorted yet?

arrays,sorting,time-complexity,mergesort,insertion-sort

Worst case complexity of Insertion sort & Quick Sort is O(n^2). Worst case complexity of merge sort is O(n*log(n)) therefore, for insertion sort & quick sort no. of steps are (10^6)^2 = 10^12 so it takes 10^12/10^8 = 10^4 or 10,000 seconds = 2.77hrs (as CPU operates 10^8 steps/sec) where...

c,sorting,linked-list,mergesort

if ( data == NULL ) return; You should return NULL. btail = head->next; // second item while(btail->next != NULL) // anything left { If btail is set to head->next. If head->next is NULL, you're trying to check in the loop NULL->next != NULL which isn't a thing. if( btail->next...

sorting,time-complexity,mergesort

The runtime of mergesort is Θ(n log n). For sufficiently large n (like the numbers you have here), it's not unreasonable to model the runtime as some function of the form cn log n. One way to approach this problem would be to think about the ratio of the runtime...

You can`t assign a Array to a list. Try this.customerList= Arrays.asList(values); or Change the method parameetr to List<Customer> public void sort(List<Customer> values) { ...

The problem for your solution is the result may be larger than the integer range, for example, if the sequence are n, n - 1, ... , 1, (non increasing) the number of inversion will be n*(n - 1)/2 and with n = 2*10^5, the result will be much larger...

java,multithreading,algorithm,parallel-processing,mergesort

Why would this algorithm run fastest with 4 threads on a dual core cpu? This could simply be an artefact of poor benchmarking. For example, if your benchmark does not take proper account of JVM warmup effects, the results won't be reliable. Beyond that, the "hyperthreading" explanation is plausible:...

algorithm,sorting,time-complexity,mergesort,insertion-sort

It's hardly possible to determine values of these constants, especially for modern processors that uses caches, pipelines, and other "performance things". Of course, you can try to find an approximation, and then you'll need Excel or any other spreadsheet. Enter your data, create chart, and then add trendline. The spreadsheet...

Python-ish pseudocode: while lft and rgt: #NEITHER HALF IS EMPTY if lft[-1] >=rgt[-1]: #lft HAS GREATEST LAST VALUE # if the last of lft is greater than the last of rgt (which is sorted), # then it is also greater than everything before the last element of rgt, # so...

recursion,mergesort,master-theorem

The recursion tree for the given recursion will look like this: Size Cost n n / \ 2n/5 3n/5 n / \ / \ 4n/25 6n/25 6n/25 9n/25 n and so on till size of input becomes 1 The longes simple path from root to a leaf would be n->...

Here's some code for you to look at. This starts with recognizing that the file is already a collection of single elements. Therefore we can do the first grouping/sorting when we read the file. Since arrays are very impractical for this part I used Lists and then cast the return...

I think is a duplicate question from this where the explanation is very clear. Is not in C++ but I think it is enough to understand excluding the language.

int merge(int *ar,int low,int mid, int high){ int temp[8]; int i,j,index,k; k=0; index=0;//temp's index start 0; i=low; j=mid+1; while(i<=mid && j<=high){ if(ar[i]<ar[j]){ temp[index++] = ar[i]; i++; }else{ temp[index++] = ar[j]; j++; } } while(i<=mid){ temp[index++] = ar[i]; i++; } while(j<=high){ temp[index++] = ar[j]; j++; } for(k=low, index=0;k<=high;k++){//k include high ar[k]=temp[index++];...

Your main mistake is in the design of this loop: while(iterL != left.end()) { iterR=right.begin(); while(iterR != right.end()) { if(*iterR < *iterL) { //cout << "Pushing back " << *iterR << endl; output.push_back(*iterR); } iterR++; } //cout << "Pushing back " << *iterL << endl; output.push_back(*iterL); iterL++; } Consider what...

The general approach: if( list contains 0 or 1 item) return the list; // it is already sorted split the list into halves; mergesort( first part); mergesort( second part); merge sorted parts; return the merged list; A list contains 0 or 1 item condition: head == NULL || head->next ==...

When calling MergeSort you are recursively returning new lists but, are never assigning them: def Merge(left, right): result = [None] * (len(left) + len(right)) i, j, k = 0, 0, 0 while i < len(left) and j < len(right): if left[i] < right[j]: result[k] = left[i] #result.append(left[i]) i += 1...

java,algorithm,sorting,mergesort,selection-sort

You have: private void MergeSort(int[] array, int low, int high) throws InterruptedException { int[] temp = new int[array.length]; Of course allocating an array of length 5000 to 50000 at each step of the recursion will make the algorithm much slower. Try to reuse the same temp array....

Although it's not clear why you're sorting arrays of pointers-to-ints instead of just copying the ints themselves, it's definitely leading you astray. When you say: if ((*pointerArray)[leftIndex] <= (*pointerArray)[rightIndex]) you're not comparing what you intend to. *pointerArray is the same as pointerArray[0], or the int * that's first in the...

What's the number of inversions in the array a? It equals the number of inversions in first half of the array a(X) plus number of inversions in the second half of the array a (Y) and number of inversions where one element is in the first half and another is...

algorithm,mergesort,asymptotic-complexity

To merge two lists of size M, you need 2M-1 comparisons, for O-purposes we can ditch the -1. For a list of length N, you need to go do dividing and merging on log(N) levels, in each of those you have less than N comparisons. That makes a total number...

algorithm,sorting,haskell,functional-programming,mergesort

myMergeSort is not a correct merge sort. It is a correct insertion sort though. We start with an empty list, then insert the elements one-by-one into the correct position: myMergeSort [2, 1, 4, 3] == foldl merge [] [[2], [1], [4], [3]] == ((([] `merge` [2]) `merge` [1]) `merge` [4])...

Here is my version of your mergeSort, with the merge function extracted: def mergeSort (unSortedList): if len(unSortedList) == 1 : return unSortedList else: midpoint = len(unSortedList)//2 A = mergeSort (unSortedList[:midpoint] ) B = mergeSort (unSortedList[midpoint:] ) return merge(A, B) def merge(a, b): i = 0 j = 0 c =...

I think this should explain what is happening: matt$ python >>> '19' < '2' True >>> int('19') < int('2') False When comparing strings, the string '19' is less than the string '2' because the character '1' comes before the character '2'. If you convert the strings to numbers, the sorting...

c++,while-loop,mergesort,insertion-sort

The conditional in while (insertionSortTime < mergeSortTime) is false in the first iteration when both insertionSortTime and mergeSortTime are set to zero. That explains why the loop never got executed. Perhaps you meant to use: while (insertionSortTime <= mergeSortTime) ...

You might have problems with your algorithm but what stands out is a very bad memory handling bug. When you say: int *leftArray = new int(sizeLeft); You allocate memory for single int and initialize it with the value of sizeLeft. That's clearly not what you want. If you want to...

swift,generics,nested,mergesort,nested-generics

Looks like you've found a bug in the compiler related to nested generic functions. Here's a reduction that also crashes the 1.2 compiler: func f<T>(t: T) { func g<U>(u: U) { } } But in this case, you don't actually need a generic version of merge. Its generic parameter is...

data[Size] attempts to get the Sizeth value from the array data. Size doesn't exist, and I don't think this is what you want. If you want to refer to the array itself, just use it's name: data. You have the same problem later on with data[size], except size does exist...

c++,algorithm,sorting,mergesort

The problem is in this part of your code: while( i <= m-1 && j <= r ){ if( A[i] <= A[j] ){ //You only count the inversions, but forgot to sort the array. i++; }else{ j++; inv_count+= m-i; } } And for sorting issue, we should create a temp...

c++,comparison,mergesort,istream,peek

peek() peeks ahead at the next character in the file. In your case, the next character in the file after "40" is a space character, ASCII space, or 32, which is less than 40....

If you have a look at the documentation to System.arrayCopy, it expects as the second argument an index into the array. However, you have there a value from your array. So most probably you wanted to write System.arraycopy(right, rightIndex, ... instead of System.arraycopy(right, right[rightIndex], ... The same for your second...

I got the answer.The correct solution is posted below. #include<iostream> #include<vector> using namespace std; void merge(vector<int> &array,int low,int mid,int high) { vector<int> helper(array); //helper = array; // copy vector elements i .. copying references doesnt work hence int current = low; int helperLeft = low; int helperRight = mid+1; while(helperLeft<=mid...

python,list,python-3.x,recursion,mergesort

When you write a recursive function, you should be careful about the base case, which decides when the recursion should come to an end. In your case, the base case is missing. For example, if the list has only one element, then you don't have recursively sort it again. So,...

c,arrays,sorting,pointers,mergesort

It is not the problem of Ctrl+D not work but your algorithm. Please change while ((i < length/2) && (j < length)){ if (a[i] < a[j]){ w[k] = a[i]; i++; k++; } else if (a[j] < a[j]){ w[k] = a[j]; j++; k++; } } to while ((i < length/2) &&...

Your Merge() signature does not match how you invoke it: Signature: void Merge(int *A,int *L,int leftCount, int *R, int rightCount) Invokation: Merge(A,L,R,mid,n-mid); This causes undefined behavior when you parse (and later use) a pointer (R) as an integer (leftCount), and an integer (mid) as a pointer (R). Pretty sure your...

In your main function, I found the following line: merge_sort(head) << endl; which tries to invoke the method operator<< on the return value of merge_sort which is impossible, because merge_sort is a void. I think this will behave as expected: std::cout << merge_sort(head) << std::endl; As you can see, I...

The problem is that you are computing the number of entries in temp incorrectly: your code thinks it is right_high + 1, but the correct formula is right_high - left_low + 1. For example, when a call gives you indexes 10, 15, 16, 26, your code tries to merge 27...

Long story short, it's because your type parameter is actually being erased to Comparable. Remember, generics are erased to their bounding type. In most cases, where there is no bounding type, type parameters would be erased to Object, but here, because you're bounding T by Comparable, T is erased to...

sorting,computer-science,mergesort

If you keep dividing n by 2, you'll eventually get to 1. Namely, it takes log2(n) divisions by 2 to make this happen, by definition of the logarithm. Every time we divide by 2, we add a new level to the recursion tree. Add that to the root level (which...

I dont understand why do you people want the long way.. Even though there are already easy way of doing this... I made one myself hope this will help you.. - (NSArray *)arrayMergeSort:(NSArray *)targetArray { if (targetArray.count < 2) return targetArray; long midIndex = targetArray.count/2; NSArray *arrayLeft = [targetArray subarrayWithRange:NSMakeRange(0,...

you are printing in each recursion of merge(), thats why you are getting it like that, as the print happens as and when a merge happens and does not just print the end result. for(int i = 0; i < high; i++){ cout << array[i]; } To avoid this, print...

A number of things... Firstly, this is a recursive function, meaning you cannot create a list within the function, as you did here: result=[] This will simply reset your list after every recursive call, skewing your results. The easiest thing to do is to alter the list that is passed...

c++,arrays,sorting,mergesort,bad-alloc

Your merge function has a memory leak, and a very big one: L = new int[n1]; R = new int[n2]; The memory is never deallocated. If you're coming from a language such as Java or C#, you see that C++ works differently. There is no automatic garbage collection, and using...

erlang,mergesort,tail-recursion

Your merge-sort is not tail recursive because the last function called in mergesort/3 is merge/3. You call mergesort as arguments of merge so stack has to grow - upper called mergesort/3 is not yet finished and its stack frame can't be reused. To write it in TR approach you need...

The flaw is that your merge doesn't copy symbols from right part if left[i1] - right[i2] > 0. This works: public static void merge(char[] string, char[] left, char[] right) { int i1 = 0; int i2 = 0; for (int i = 0; i < string.length; i++) { if (i1...

java,algorithm,bitmap,big-o,mergesort

For one thing, the Programming Pearls articles were written before the impact of memory hierarchy became as severe as it is today. A map of 800K bytes adds lots of random access memory traffic very likely to cause cache misses. Mergesorts tend to have good local memory performance.

c#,algorithm,sorting,mergesort

You have an error in your implementation Where you have: static void MergeSort(int[] a, int start, int end) { if (start != end) { int n = (start + end) / 2; MergeSort(a, 0, n); MergeSort(a, n + 1, end); MainMerge(a, start, (n + 1), end); } } you should...

To do the merge sort you are going to have to break up the list. For example always splitting on head and tail is pointless. It would always be splitting on the whole list, not the increasingly smaller portions of the list. So your split would have to look something...

When the two recursive sort routines return, you can safely assume that they have sorted their parts. The merge step combines these two sorted sub arrays. If the input is 3 5 1 8 2, the first recursive call sorts the first half and yields 3 5, the second recursive...

I guess you tested with Python lists when you found the code working very well. Now you a using it with a NumPy array. The crucial difference is that slicing a NumPy array as in here lefthalf = alist[:mid] righthalf = alist[mid:] creates views over the original array, while slicing...

c,string,sorting,mergesort,heap-corruption

void mergesort_pot2(char *key[], int n) { int j, k; char **w; w = calloc(n, sizeof(char*)); for (k = 1; k < n; k *= 2) { for (j = 0; j < n - k; j += 2 * k) merge(key + j, key + j + k, w +...

Firstly, although this is Groovy and therefore the negative index highlighted by @Useless won't throw an exception, it is indicative of a problem. I think you have two problems: Caveat: I'm not familiar with the exact presentation in "Introduction to Algorithms" Your indices into A to populate L and R...

c++,algorithm,sorting,mergesort

There are couple of things gone wrong in the implementation of your logic. I have indicated them clearly below: void merge(int*a,int p,int q,int r){ //function to merge two arrays int n1= (q-p); // size of first sub array int n2= (r-q); // size of second subarray int c[n1+1],d[n2]; //you need...

It actually is possible, though not straightforward, to implement an in-place merge sort for arrays. With linked lists the problem becomes quite simple. Each node in a linked list just has a value and a pointer to the next node. It is quite simple to break a linked list in...

c++,linked-list,stack-overflow,mergesort

So you have three recursive functions. Let's look at the maximum depth of each with the worst case of a list of 575000 elements: merge(): This looks to iterate over the entire list. So 575000 stack frames. split(): This looks to iterate over the entire list in pairs. So ~250000...

java,multithreading,performance,sorting,mergesort

There are several factors here. First of all, you are spawning too many threads. A lot more than the number of cores your processor has. If I understand your algorithm correctly you are doing something like log2(n) at the bottom level of your tree. Given that you're doing processor intensive...

algorithm,data-structures,mergesort,recurrence

I like to look at it as "runs", where the ith "run" is ALL the recursive steps with depth exactly i. In each such run, at most n elements are being processed (we will prove it soon), so the total complexity is bounded by O(n*MAX_DEPTH), now, MAX_DEPTH is logarithmic, as...

java,recursion,merge,queue,mergesort

This is the updated code which is running OK with no compilation and run-time error: public class Merge { public static void mergesort(int arr[], int low, int high) { int middle; if(low<high) { middle = (low+high)/2; mergesort(arr,low,middle); mergesort(arr,middle+1,high); merge(arr,low,middle,high); } } public static void merge(int arr[], int low, int middle,...

Suppose you input a vector of size 2; then according to your code mid=1; for(int i=0;i<mid-1;i++) // here i < (1-1) which will never execute l[i]=v[i]; ...

This part of code will merge remaining elements. For example if you have {3,4} and {1,2,6,7} to merged then the part above this if(h>pivot) condition gives {1,2,3,4}. So to copy rest elements we use this conditions....

Change this while (j < leftSize) { arr[k++] = right[j++]; } To while (j < rightSize) { arr[k++] = right[j++]; } ...

Think of it like sorting a 128 sheets of paper with numerals written on them. The first step is to arrange adjacent sheets. You have to touch/move all 128 sheets to do that. The next step is to merge pairs into groups of four. Again you need to move all...

javascript,algorithm,sorting,merge,mergesort

Just replace i + 1 by i and j + 1 by j in all while loops' conditions and it will work properly. Currently the last elements of a and b are just ignored because their indices are a.length - 1 and b.length - 1, respectively.

There are several issues... Don't use List#add, use List#set Instead of... while(helperLeft <= middle && helperRight <= high) { if(helper.get(helperLeft).isLessThan( helper.get(helperRight))) { list.add(current, helper.get(helperLeft)); helperLeft++; } else { list.add(current, helper.get(helperRight)); helperRight++; } current++; } //Copy remaining elements int remaining = middle - helperLeft; for(int j=0; j <= remaining; j++) {...

As 32 is 25, the recursion tree will be a full binary tree. We then do 1 + 2 + 4 + 8 + 16 + 32 = 63 calls to mergesort. It is unclear to me why the answer would be 31, when they state the base case is...

The way mergesort works is dividing the array in two arrays, recursively (logn times), untill being able to compare pairs of elements. Then it merges the recursively created arrays also sorting them at the same time. For some sorting algorithms (e.g. quicksort), the initial order of the elements can affect...

sorting,quicksort,binary-search,mergesort

After some Googling and testing, I finally got the answer: In case of Binary Search, when I tried it for the input 20,21 and 30, searching for the element 20, I finally landed upon a typical case wherein p=r=0. If the base condition included here is p>=r, then the result...

c++,arrays,parameters,mergesort

If you've named your variables in the obvious way then (aside from congratulating you for doing that) &(array[size]) is probably returning a pointer to 1 beyond the bounds of array. Dereferencing that pointer will give you undefined behaviour as you don't own that memory,. I think you mean to pass...