Basic CS [Redpine Infotech Placement]: Sample Questions 13 - 13 of 13

Glide to success with Doorsteptutor material for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

Question 13

Basic CS
Edit

Describe in Detail

Essay▾

Merge sort problem can be solved using which method.

Explanation

Given Divide and Conquer Method
  • Merge sort problem can be solved using divide and conquer strategy.
  • The problem is divided into smaller sub-problems and each one solved independently.
  • When we divide the subprograms into even smaller sub-programs, we reach a stage where no more division is possible.
  • Those “atomic” smallest possible sub-programs are then solved.

Merge Sort Problem

  • Based on divide and conquer technique.
  • First divides the array into equal halves and then combines them in a sorted manner.

    Ex

    Merge sort, will take an unsorted array as below:

Merge Sort Problem
  • Divide first equal into two parts.
  • Array of 8 items is divided into two array of size 4.
8 Items is Divided into Two Array
  • Does not change sequence of item.
  • We divide these two arrays into further equal parts.
Two Arrays into Further Equal Parts
  • Further divide these array
Divide These Array
  • Now, we combine them in exactly the same manner they broken down.
  • We see the 18 and 32 are in sorted positions.
  • We compare 26 and 9 and in the target list of 2 values, we put 9 first, followed by 26.
  • We change the order of 17 and 35 whereas 42 and 46 are placed sequentially.
Change the Order
  • We compare lists of two data values, and merge them into list of found data values placing all in a sorted order.
Lists of Two Data Values
  • The final merging is below:
The Final Merging
  • This is solution of merge problem.

Developed by: