Question

Describe a variation of the merge-sort algorithm that is given a single array, S, as input,...

Describe a variation of the merge-sort algorithm that is given a single array, S, as input, and uses only an additional array, T, as a workspace. No other memory should be used other than a constant number of variables. Compare the time complexity of the variation to the normal merge-sort algorithm.

Homework Answers

Answer #1

ANSWER :

Step 1 - If it is only one element in the array S it is already sorted, return.
Step 2 - divide the array recursively into two halves until it can no more be divided.
Step 3 - merge the smaller arrays into new array T in sorted order.And store merged sorted array in array S.


MergeSort(S[], l, r ,T[])
If r > l
1. Find the middle point to divide the array into two halves:  
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(S, l, m ,T)
3. Call mergeSort for second half:
Call mergeSort(S, m+1, r ,T)
4. Merge the two halves sorted in step 2 and 3 and store it in temporary array T:
Call merge(S, l, m, r , T)
5. Restore back the sorted merged array T into array S .

I tried my best... hope it helps... please give an upvote. it's very important to me.. thank you:)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Implement functions for insertion sort, quicksort, heapsort and merge sort that input an array of integers...
Implement functions for insertion sort, quicksort, heapsort and merge sort that input an array of integers and sort it in-place. Write a program that generates random integer arrays (hint: use seed appropriately to avoid generating same sequences) of lengths 10, 100, 1000, 10,000, 100,000, 1000,000, and then sorts each using each of the sorting functions from (a), and measures the time in nanoseconds. The program will repeat this process 30 times and will compute the average execution time for each...
Given a large array of several million elements of type 'double', you are asked to sort...
Given a large array of several million elements of type 'double', you are asked to sort them in ascending order using an algorithm of your choice. You choose selection sort. Why is this a poor choice? Group of answer choices Selection sort can only sort elements of type 'int' Selection sort requires 3x the memory of other sort algorithms Selection sort can only work on an array with an odd number of elements Selection sort will be prohibitively inefficient for...
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
Using C++, Python, or Java, write a program that: In this programming exercise you will perform...
Using C++, Python, or Java, write a program that: In this programming exercise you will perform an empirical analysis of the QuickSort algorithm to study the actual average case behavior and compare it to the mathematically predicted behavior. That is, you will write a program that counts the number of comparisons performed by QuickSort on an array of a given size. You will run the program on a large number of arrays of a certain size and determine the average...
Suppose you are given a set S = {a1,a2,···,an} of tasks, where task ai requires pi...
Suppose you are given a set S = {a1,a2,···,an} of tasks, where task ai requires pi units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let ci be the completion time of task ai, that is, the time at which task ai completes processing. Your goal is to minimize the average completion time, that is, to minimize n1...
Write a program of wordSearch puzzle that use the following text file as an input. The...
Write a program of wordSearch puzzle that use the following text file as an input. The output should be like this: PIXEL found (left) at (0,9). ( Use JAVA Array ) .Please do not use arrylist and the likes! Hints • The puzzle can be represented as a right-sized two-dimensional array of characters (char). • A String can be converted into a right-sized array of characters via the String method toCharArray. . A word can occur in any of 8...
Use a few sentences to describe the problem given below . Also, Identify the nouns and...
Use a few sentences to describe the problem given below . Also, Identify the nouns and verbs used in the below project descriptions.  Identified nouns, list the ones that are necessary to define variables in your program. For each variable, specify its name, data type, and what information it is used to store. Write the pseudo code algorithm (i.e. algorithm steps) to solve this problem. (For the base salaries and commission rates use constants instead to keep these values. Use the...
**please write code with function definition taking in input and use given variable names** for e.g....
**please write code with function definition taking in input and use given variable names** for e.g. List matchNames(List inputNames, List secRecords) Java or Python Please Note:    * The function is expected to return a STRING_ARRAY.      * The function accepts following parameters:      *  1. STRING_ARRAY inputNames      *  2. STRING_ARRAY secRecords      */ Problem Statement Introduction Imagine you are helping the Security Exchange Commission (SEC) respond to anonymous tips. One of the biggest problems the team faces is handling the transcription of the companies reported...
Consider the C program (twoupdate) to demonstrate race condition. In this assignment, we will implement Peterson's...
Consider the C program (twoupdate) to demonstrate race condition. In this assignment, we will implement Peterson's algorithm to ensure mutual exclusion in the respective critical sections of the two processes, and thereby eliminate the race condition. In order to implement Peterson's Algorithm, the two processes should share a boolean array calledflagwith two components and an integer variable called turn, all initialized suitably. We will create and access these shared variables using UNIX system calls relating to shared memory – shmget,...
C++. Write a program that draws a rocket shape on the screen based on user input...
C++. Write a program that draws a rocket shape on the screen based on user input of three values, height, width and stages. The type of box generated (i.e.. a hollow or filled-in) is based on a check for odd or even values input by the user for the box height (or number of rows). Here is the general specification given user input for the height of the box..... Draw a hollow box for each stage if the value for...