Closed

Java recursive and iterative merge sort

Recursive version

Divide and conquer - split into two parts arbitrarily, sort both parts and then merge them together to complete the sort.

There are two ways of splitting, odds and evens or left and right, leading to quite different implementations. There is also an approach called natural merge sort where we make use of

existing sorted (and/or reverse sorted) sequences.

The following outlines the left-right method which will be more efficient if the data structures exceed the amount of physical memory. Also if the left element is always merged before

the right element when they compare equal, the algorithm will be stable (not mess with the order of equal elements).

Note that there is a redundant copy after each merge - it is possible to avoid this by swapping which is source and which is target each time (one mark off for excessive copying).

mergeSort(objects, left, right)

1. declare a second array of the same size to use for merging;

2. define the left and right bounds of the array defining a subarray;

3. if there are less than two elements there is nothing to do and the subarray is sorted;

4. if there are two or more elements,

- sort the left subarray and the right subarray this way;

- merge the sorted subarrays into the second array;

- copy the merged subarray back into the original array.

merge(a, b, left, right, size)

1. initialize target = left, lbound = right, rbound = size

2. while left < lbound and right < rbound

- if a[left] <= a[right], move it to b[target] and increment left and target

- else a[right] < a[left], move it to b[target] and increment right and target

3. move across the rest of whichever side hasn't been copied yet.

Iterative version

Hint. You don�t actually need a stack and will get an extra mark if you avoid it. The splitting is purely conceptual - nothing changes in the array until you merge. Initially you will be merging single elements into pairs, then pairs into quads, then quads into octets, ... You might likely to consider in the recursive versions of quicksort and mergesort just where the

work happens (on the way in or the way out). This also relates to the idea of top-down and bottom up. In iteration you don�t need to model both halves of the recursive process

(down/into deeper levels and up/out of the deeper levels).

In producing an iterative version you may find it convenient to assume y

Skills: Algorithm, Java

See more: difference between iterative merge sort and recursive merge sort, recursive merge sort in data structures, iterative merge sort in data structures, iterative merge sort c++ code, iterative merge sort java, merge sort iterative vs recursive, iterative merge sort python, iterative merge sort linked list, java code read write sort text file, java linked list quick sort, merge sort apache logs, iterative quick sort java, java code program quick sort, java link list quick sort sample, merge sort java, merge sort, merge sort algorithm java, merge sort using thread, programming merge sort huffman coding, thread merge sort

About the Employer:
( 10 reviews ) Hyderabad, India

Project ID: #19300680

11 freelancers are bidding on average ₹2207 for this job

it2051229

Hi there, I went through your requirements and I would like to do this project if given the opportunity. Let me know if you are interested because I know merge sort very well.

₹1500 INR in 1 day
(1095 Reviews)
7.6
utkarshkatiyar19

Hi I'm an expert in java programming and merge sort as well. I'm sure that I can easily do this project. We can have a about it. Thanks..

₹5000 INR in 2 days
(317 Reviews)
7.2
koustav2006

HI...I am proficient in algorithm implementation in core Java including recursive merge sort as per given instructions and can help you write the Java code.

₹2777 INR in 1 day
(151 Reviews)
6.1
MichealSMoreno

Dear client. I've read your project description carefully and very interested. Let's discuss over chat and get started. Waiting for your reply. Best regards.

₹5000 INR in 1 day
(11 Reviews)
3.5
i0xHeX

Hello, I'm java developer with 3 years experience. I read the task about merge sort and can complete it in 1 day or less. The only question - what type of data to sort? Feel free to contact me. Thanks.

₹1500 INR in 1 day
(14 Reviews)
3.4
VadimShutenko

Hello, I work as a private assistant for students. I have done many tasks for my students: games, algorithms, data structures and many others. I've made this task two or three times. I'm sure I can help you.

₹1150 INR in 1 day
(1 Review)
1.1
miotek32

I prepare a complete algorithm in any language then you want. I prepare this program in half of day.

₹1300 INR in 10 days
(0 Reviews)
0.0
AbdullahNIK

Hi there. I have worked on data structures and algorithms for over 2 years. i have great knowledge on java/C++/C#/python and some other languages. i am sure i will satisfy you with what you require if you give me the c More

₹1750 INR in 3 days
(0 Reviews)
0.0
CalieRizz

Hello! I have a degree in software engineering and worked with sorting algorithms before, as mergesort, quicksort, bubblesort, and would love to help you.

₹2350 INR in 1 day
(0 Reviews)
0.0
sk5519

Hello, I have in-depth knowledge in data structures and using java for the past 3 years. I also solved many similar problems in hacker rank using java. My hackerrank profile is [login to view URL] More

₹700 INR in 1 day
(0 Reviews)
0.0
shrishailsm

Ill delver the project in a day. Got 10 years of experience in java programming. Consider my proposal.

₹1250 INR in 1 day
(0 Reviews)
0.0