Suppose the following array were passed in to a mergesort algorithm: 42 39 87 21| 56 93 43 35 Draw what the array looks like after the first recursive call completes, and then after the second recursive call (immediately before the final call to merge).

Suppose the following array were passed in to a mergesort algorithm: 42 39 87 21| 56 93 43 35 Draw what the array looks like after the first recursive call completes, and then after the second recursive call (immediately before the final call to merge).

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter18: Stacks And Queues

Section: Chapter Questions

Problem 16PE: The implementation of a queue in an array, as given in this chapter, uses the variable count to...

See similar textbooks

Related questions

Q: Given these 8 numeric values to be sorted using the recursive Mergesort algorithm: 92 63 24 18 69…

A: Merge sort is the sorting technique which uses merging procedure to sort the elements and it good…

Q: Given the unsorted list [6, 5, 4, 3, 7, 1, 2], show what the contents of the list would be after…

A: a. Selection sort:[6, 5, 4, 3, 7, 1, 2][1, 5, 4, 3, 7, 6, 2][1, 2, 4, 3, 7, 6, 5][1, 2, 3, 4, 7, 6,…

Q: The bubble sort algorithm is used to sort the following sequence of integers: 3 32 19 41 27 20 7…

A: Given :- The bubble sort algorithm is used to sort the following sequence ofintegers: 3 32 19 41 27…

Q: Perform a selection sort on the following unsorted list: 3 2 5 6 4 1 In each blank, enter the list…

Q: Write the state/order of the elements of the following array after each pass of the outermost loop…

A: Insertion Sort Insertion sort is simple sorting mechanism in which final sorted array is…

Q: Suppose you have the following sorted list [3, 5, 6, 8, 11, 12, 14, 15, 17, 18] and are using the…

A: Given a sorted array : [3, 5, 6, 8, 11, 12, 14, 15, 17, 18] Size of array : 10 Subscript Range : 0-9…

Q: convert this python code into java? Python code is as shown below: # recursive function def…

A: Given: convert this python code into java? Python code is as shown below: # recursive function def…

Q: Selection sort is a sorting algorithm, like Bubble sort which you saw in the previous module.…

A: Given function index_of_min(I,start_index), Function returns the next minimum index from the given…

Q: Present an example of walking through the merge sort or the quick sort algorithm (your choice) This…

A: Merge Sort is a an example of Divide and Conquer algorithm. It divides the input array and then…

Q: Write a python program to implement Breadth first search Traversal.

A: Introduction: Here we are required to create a program in python to implement Breadth first search…

Q: Write a java method to search for an element in an array using a linear search. Many list processing…

A: Use a recursive function which accepts 4 parameters, one is the list, second is the search value,…

Q: Answer the following regarding Merge Sort: Select 1. Merge Sort requires an additional space (apart…

A: Merge sort works on the principle of Divide and Conquer. It repeatedly breaks down a list into…

Q: Show how the Mergesort algorithm sorts your array by: 1) Showing which sub parts of the array are…

A: The program is written in Python. check the program screenshot for the correct indentation. Please…

Q: as a pivot is a very effective strategy for Quicksort. C. Both Quicksort and Insertion sort are

A: Explanation: Because Quick Sort has extra cost from the recursive function calls, insertion sort is…

Q: Explain how to answer the following questions The sorted values array contains the sixteen integers…

A: Step 1:- Note:-I am giving the solution of first three question. Introduction:- A binary search is…

Q: Write intermediary ordered list after each recursive merge step when calling merge sort on (4, 8, 5,…

A: Below is the answer to the above question. I hope this will be helpful for you..

Q: Q 1. How recursions are implemented in context to activation records? Give an example. (Example of…

A: 1) RECURSION: Recursion is a function that calls itself for several number of times.…

Q: Consider the following array of int values. [17, 11, 6, 22, -3, 8, 4, 22, 2, 35, -4, 10] Write the…

A: Selection sort: Elements in array: [17, 11, 6, 22, -3, 8, 4, 22, 2, 35, -4, 10] Pass 1: Find the…

Q: During Mergesort operation, two recursive calls are made. Which option is correct after these…

A: Merge sort follows the divide and conquer algorithm in which partition the list into two sub lists…

Q: Based on the array named B in the figure below, write the Quick sort partition work trace for cut =…

Q: Based on the array named dataQ in the figure below, write the Quick sort partition work trace for…

A: As mentioned I have given the direct answers for cut=partition(dataQ,0,4)

Q: Implement a merge sort algorithm have a mergesort function and a merge function Go off this code…

A: We have to Implement a merge sort algorithm that has a mergesort function and a merge function as…

Q: write a Python Program for Binary Search (Recursive and Iterative)

A: Below program implements two funnctions to find the index of an element in a list…

Q: (IN C++) Write a program to implement Quicksort. Also implement one of the slow sorts (Bubble,…

A: ANSWER:-

Q: Python code is as shown below: # recursive function def row_puzzle_rec(row, pos, visited): # if the…

A: Given:

Q: Write a Java program to implement Merge Sort algorithm for sorting a list of integers in descending…

A: Given input : 56,23,40,82,12,34,97,66,49 We need to implement Merge sort algorithm for sorting above…

Q: Consider the Sort-and-Count algorithm explained in section 5.3 of our text: "Counting…

A: Given:Initial list:26 81 87 32 66 72 86 97 23 48 14 71 89 18 49…

Q: Modify the following algorithm of Merge Sort in such a way that during every recursive call it…

A: Merge Sort is a Divide and conquer algorithm. It divides the input array into two halves, calls…

Q: A particular sorting algorithm takes integer list 10, 6, 8 an incorrectly sorts the list to 6, 10,…

A: Below is the answer with explanation:

Q: Show a complete run of Quicksort on the following array X : X: 1 2 3 4 5 6 7 8 9 10 17 5 -3 40 46 50…

A: Given array X: {1, 2 ,3 ,4 ,5 ,6, 7 ,8 ,9 ,10 17, 5, -3 ,40 ,46 ,50 ,16, 0, 22, 4}

Q: the list has the following items 17 9 11 30 8 20 35 7 5 45 3 28 Apply the quick sort on the…

A: The given elements are: 17 9 11 30 8 20 35 7 5 45 3 28 0 1 2 3…

Q: Write intermediary ordered list after each recursive merge step when calling merge sort on {4, 8, 5,…

A: Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several…

Q: The CPU of a computer handles the processes using shortest-job-first policy, which means, given the…

A: We are given shortest-job-first policy to schedule the processes. And we are asked about the data…

Q: Design and implement an algorithm using recursion and backtracking to sort an array of integers into…

A: Note: Since the language in the question is not defined so I am using python to implement this…

Q: Show how the Mergesort algorithm sorts your array by: 1) Showing which sub parts of the array are…

A: Merge sort algorithm is used to sort the elements of the array using the merge procedure. It is…

Q: 1. Imagine there are 50 nodes in a queue and the head and the tail are pointing to the one and the…

A: Since you have asked multiple questions, we will answer the first one. If you want any specific…

Q: in C Implement the QuickSort algorithm. - For n=3 the algorithm uses the rearrange function with…

A: Quick sort algorithm is a sorting algorithm which uses partition procedure to sort. It is best…

Q: Consider the following recursive algorithm: Int active(Int lst [1.int lowerindex, Int upperindex)…

A: As per our guidelines, we are supposed to answer only one question. Kindly repost the remaining…

Q: Exercise 1 Given the following recursive version of selection sort: public void…

A: The question is to write the corrected code for the given problem. The JAVA language has been used…

Q: Question 1) Implement Merge sort and Quick sort on a programming language of your choice. Evaluate…

A: The result for each sorting algorithm is given below:-

Q: how the contents of a (linear) queue and position of front and rear markers (at each step) once the…

A: Queue data structure follows FIFO (first in first out) strategy to perform insert and delete…

Q: Show all steps that recursive merge sort algorithm would perform to sort the list of values…

A: The solution to the given problem is below.

Q: Juestion which of the following statements about mergesort are true? Unless otherwise specified,…

A: Merge sort is an efficient sorting algorithm which is based on divide and conquer rule. Here is the…

Q: (a) Merge Sort uses what sort of optimisation: greedy, backtracking or divide and conquer? MergeSort…

A: With our restriction on number of questions we can solve the first one only. - The question is to…

Q: Given the following non-recursive implementation of depth-first search: A. Complete the…

A: Answer: I have completed the code in C++ programming language

Q: A merge sort is used to sort an array of 1000 test scores in descending order. Which of the…

A: Answer of the given question choice (d) is the correct answer The complete explanation is given in…

Concept explainers

Randomized Select Algorithm

A randomized algorithm is defined as one that uses a certain amount of randomization in its logic or operation. It is said to be an algorithm that depends on the random number to perform its operation. It is used for reducing the overall time complexity, space complexity in the standard algorithm. The randomized algorithm uses the concept of random numbers to find the solutions to the different kinds of problems and also to improve the problem solutions.

Question

Suppose the following array were passed in to a mergesort algorithm:
42
39 87
21 56
93
43
35
and
Draw what the array looks like after the first recursive call completes,
then after the second recursive call (immediately before the final call to
merge).

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Step 1

VIEW

Step 2

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 2 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

Finish the splitOdd10 using recursion to determine if the elements of an array can be split into two groups such that the sum of one group is a non-zero multiple of 10 and the sum of the other group is odd
The question below is about Quicksort. Consider the array of ten integers #(55 54 61 79 40 65 70 40 54 38 1. Write again the array of ten integers (this will facilitate marking your answer, in case you write it on a separate paper). 2. What would be the contents of the array immediately before the first recursive call to quicksort? In your answer, trace the algorithm by showing the contents of the array each time an array element is swapped.
Outline, but do not implement, a recursive solution for sorting an array of numbers. Hint: First sort the subarray without the initial element.
(a) Write a method public static void insert(int[] a, int n, int x) that inserts x in order among the first n elements of a, assuming these elements are arranged in ascending order. Do NOT use arraylists. x is the last element in a. n does not include x. (b) Using the insert method from Part (a), write a recursive implementation of Insertion Sort.
The sorted values array contains the sixteen integers 1, 2, 3, 13, 13, 20, 24, 25, 30, 32, 40, 45, 50, 52, 57, 60. How many recursive calls are made by our binarySearch method given an initial invocation of binarySearch(45, 0, 15)? A. 3. B. 1. C. 4 D. 2. E. 0 A recursive definition is a definition (choose the best answer): A. that is recursive. B. in which something is defined in smaller terms of itself. C. which uses a mathematical equation. D. where a base case is defined. E. that repeats itself. Recursion is implemented by the system: A. using run time storage allocation. B. using static storage allocation. C. using a single static "stack frame". D. using compile time storage allocation.
For a recursive binary search, put the following code in the correct order by dragging each line to the correct place. 1 2 A 5 60 7 8 ⠀ :::: if (right >= left) { if (array [mid] == item) return mid; int binarySearch(int array [], int left, int right, int item) { return binarySearch(array, left, mid - 1, item); if (array [mid] > item) return binary Search(array, mid+ 1, right, item); int mid=1+ (right - left) / 2; return -1; }
// MergeSortTest.java// Sorting an array with merge sort.import java.security.SecureRandom;import java.util.Arrays; public class MergeSortTest { // calls recursive sortArray method to begin merge sorting public static void mergeSort(int[] data) { sortArray(data, 0, data.length - 1); // sort entire array } // splits array, sorts subarrays and merges subarrays into sorted array private static void sortArray(int[] data, int low, int high) { // test base case; size of array equals 1 if ((high - low) >= 1) { // if not base case int middle1 = (low + high) / 2; // calculate middle of array int middle2 = middle1 + 1; // calculate next element over // split array in half; sort each half (recursive calls) sortArray(data, low, middle1); // first half of array sortArray(data, middle2, high); // second half of array // merge two sorted arrays after split calls…
Write a Program to implement binary search using recursion.
For a Given array of Size 100, do the following implementations - 1. Write a program to implement the Modified version of the bubble sort algorithm so that it terminates the outer loop when it detects that the array is sorted. Compare the running time of the modified algorithm with Original Bubble sort. 2. Implement Quick sort ( both iterative and recursive). Calculate the run time complexity of both the implementation and compare their performance in terms of best, average and worst time complexity.
Assume you have a sorted list of 100 pre-sorted elements and a recursive implementation of Quicksort. How many calls to Quicksort are made in order to fully sort it. Assume that the algorithm makes the recursive Quicksort calls before checking if it has an array of size 1 (see https://www.geeksforgeeks.org/quick-sort/ for specific pseudo code or the textbook Introduction to Algorithms 3rd Edition page 171). 85 101 50 103 199 Assume you have the following array: 40, 20, 15, 40, 90, 60, 50, 70. Which of the following elements, if selected as the pivot, would give you the most unequal sub-arrays to be sorted using quicksort? 30, 70 20, 15 40, 90 90, 70 90, 15 Assume you have the following array: 40, 20, 15, 40, 90, 60, 50, 70. Which of the following elements, if selected as the pivot, would give you the most unequal sub-arrays to be sorted using quicksort? 30, 70 20, 15 40, 90 90, 70 90, 15 Assume we have the array 4,10,3,5,1,2,5,6,1,2,3. What are the swaps that will occur after we…
In the Recursive Binary Search shown below, there are two base cases: Line 10: the search is exhausted without a finding a value that matches the key Line 16: the search finds a value that matches the key 1 public class RecursiveBinarySearch { 2 public static int binarySearch(int[] list, int key) { 3 int low = 0; 4 int high = list.length - 1; 5 return binarySearch(list, key, low, high); 6 } 7 8 private static int binarySearch(int[] list, int key, 9 int low, int high) { 10 if (low > high) // The list has been exhausted without a match 11 return -low - 1; 12 13 int mid = (low + high) / 2; 14 if (key < list[mid]) 15 return binarySearch(list, key, low, mid - 1); 16 else if (key == list[mid]) 17 return mid; 18 else 19 return binarySearch(list, key, mid + 1, high); 20 } 21 22 public static void main(String[] args) { 23 int[] list = {3, 5, 7, 8, 12, 17,…
With the Binary Search algorithm, the algorithm can be developed by the loop-based form as well as a recursive form. Which of the following is not true? O If the item is not found, the loop version returns when the range bounds reach, but the recursive version finishes when the recursive depth is more than half the initial search range. The search range starts with the whole array, and only the recursive version can work on a subrange passed through arguments. O Both forms of the program divide the search range repeatedly in half. O If the item is found, the loop version returns from the entire method, whereas the recursive version returns from one level of recursion.