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

Habilidades: Algoritmo, Java

Veja mais: 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

Acerca do Empregador:
( 14 comentários ) Hyderabad, India

ID do Projeto: #19300680

11 freelancers estão ofertando em média ₹2207 para esse trabalho


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 em 1 dia
(1095 Comentários)

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 dias
(317 Comentários)

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 em 1 dia
(151 Comentários)

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 em 1 dia
(11 Comentários)

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 em 1 dia
(14 Comentários)

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 em 1 dia
(1 Comentário)

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

₹1300 INR in 10 dias
(0 Comentários)

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 Mais

₹1750 INR in 3 dias
(0 Comentários)

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 em 1 dia
(0 Comentários)

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] Mais

₹700 INR em 1 dia
(0 Comentários)

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

₹1250 INR em 1 dia
(0 Comentários)