• Post Reply Bookmark Topic Watch Topic
  • New Topic

Help with MergeSort algorithim  RSS feed

 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm feeding an unsorted array as an input for my mergeSort() but it's not behaving correctly and I really can't fiqure it out .
first, I think I'm getting the dividing part correctly where I ask if (low index<high index) then the array can be further subdivided into left and right parts via recursive calls


but I think I'm having issues when it comes time to combining and sorting. first, I assumed that rearranging elements would be alot more difficult using the same array so I created a global array called "sortedArray" initialized it at the main function to be of the same length as my toBeSorted array. and this is my code for the whole program
 
Marshal
Posts: 56600
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

I never try to keep algorithms in my head, so have you compared your merge sort with examples elsewhere? I think that will be the best way to find whether there is an error.
I think you are correct to keep the original array in memory as well as a copy array (why not return the copy array from the method?), so you will use double the memory, but that will only be a problem if you have a very small amount of RAM or a very large array (maybe 10⁸=10×crore elements). I think you are correct that you can subdivide the array as long as left<right. As far as I remember, you take the two adjacent 1‑element arrays and put the smaller element in the [left+0] position of the array and the larger in the [left+1] position.
Then you go back one stage in the recursion and you look whether the [left+0] element is greater or smaller than the [left+2] element, etc. I think you have the correct concepts for all the sorting stages, but there might be a tiny error which you will only see if you compare your code with an example.
 
Bartender
Posts: 3271
82
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think the problem is when you move back up the recursion tree you are comparing the original array (in it's original order) rather than the array with newly sorted elements.
 
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tony Docherty wrote:I think the problem is when you move back up the recursion tree you are comparing the original array (in it's original order) rather than the array with newly sorted elements.


Agreed. The merge part of the algorithm puts the results in a different location. Arguably, it would have worked, if the algorithm wasn't recursive or if the caller method knew where the results are stored (instead of assuming that the result is still in the original array).

Henry
 
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong wrote:(instead of assuming that the result is still in the original array)

Which is much better than what's happening now.

A lesson here is: don't use globally accessible mutable data.
 
Raed k.tabani
Greenhorn
Posts: 2
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanks Campbell Ritchie for the welcome and everyone for your answers,
it was a bit lazy from my part to just throw the code here while a lot of examples are out there, I guess I wanted to solve this on my own. I did check and I solved the issue by changing my sort() and getting rid of the global array with two local ones , each to store the left and right subarrays. and the problem was as the rest of you guys have pointed , I was comparing the unsorted original array as I was moving back up the  recursion tree

 
Tony Docherty
Bartender
Posts: 3271
82
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Glad to hear you have fixed the problem and thanks for posting your solution.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well done sorting it out
 
Stephan van Hulst
Saloon Keeper
Posts: 7993
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your method only merges two sorted array segments. It doesn't actually sort an entire array.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!