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.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

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:)

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

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...
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...
For a C program hangman game: Create the function int setup_game [int setup_game ( Game *g,...
For a C program hangman game: Create the function int setup_game [int setup_game ( Game *g, char wordlist[][MAX_WORD_LENGTH], int numwords)] for a C program hangman game. (The existing code for other functions and the program is below, along with what the function needs to do) What int setup_game needs to do setup_game() does exactly what the name suggests. It sets up a new game of hangman. This means that it picks a random word from the supplied wordlist array and...
Strings The example program below, with a few notes following, shows how strings work in C++....
Strings The example program below, with a few notes following, shows how strings work in C++. Example 1: #include <iostream> using namespace std; int main() { string s="eggplant"; string t="okra"; cout<<s[2]<<endl; cout<< s.length()<<endl; ​//prints 8 cout<<s.substr(1,4)<<endl; ​//prints ggpl...kind of like a slice, but the second num is the length of the piece cout<<s+t<<endl; //concatenates: prints eggplantokra cout<<s+"a"<<endl; cout<<s.append("a")<<endl; ​//prints eggplanta: see Note 1 below //cout<<s.append(t[1])<<endl; ​//an error; see Note 1 cout<<s.append(t.substr(1,1))<<endl; ​//prints eggplantak; see Note 1 cout<<s.find("gg")<<endl; if (s.find("gg")!=-1) cout<<"found...
When a controlled process changes from 3s control to 6s control, it implies the s of...
When a controlled process changes from 3s control to 6s control, it implies the s of the parameter remains the same. the distance between USL-LSL becomes smaller the distance between UCL-LCL becomes smaller the % of reject increases none of the above is true In a simple linear regression analysis, the following sum of squares are produced:    The proportion of the variation in y that is explained by the variation in x is: 20% 80% 25% 50% none of...
The picture shown below shows variation among three individuals with respect to 4 nucleotides - AGAT....
The picture shown below shows variation among three individuals with respect to 4 nucleotides - AGAT. What do you think what type of variation is this? AGAT different repeat numbers in different individuals .png Minisatellite Single nucleotide polymorphism Short Tandem Repeats Which of the following statements is TRUE about DNA matching? Typical difference between the genomes of human beings and Chimpanzees is estimated to be 25 % Typical difference between the genomes of human beings and Drosophila is   estimated to...
1) Describe an example of each of the following that may be found of your kitchen:...
1) Describe an example of each of the following that may be found of your kitchen: Explain how your choice falls into this category, and if there is a chemical name or symbol for it, provide that as well. Provide a photo of your example with your ID card in it. a) a compound b) a heterogeneous mixture c) an element (symbol) Moving to the Caves… Lechuguilla Caves specifically. Check out this picture of crystals of gypsum left behind in...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT