What is merge sort? What is the Time & Space Complexity for merge sort

1.	What is merge sort? What is the Time & Space Complexity for merge sort?
Answer» Merge Sort is a Divide & Conquer algorithm that is used to sort a given INPUT (can be an ARRAY or linked list). It involved dividing the input into 2 halves at each step until input has only 1 element and then merging these sorted halves to finally get a sorted input. Merge sort is not an in-place algorithm (which means you NEED to use extra SPACE for sorting the input). Merge sort is a stable algorithm which means if there are 2 same elements in the input, the sorted output will maintain the relative ordering of these elements. Time Complexity: O(NLogN) even in the WORST case. (where N is the size of the input) Space Complexity: O(N)

What is merge sort? What is the Time & Space Complexity for merge sort?

Answer»

Merge Sort is a Divide & Conquer algorithm that is used to sort a given INPUT (can be an ARRAY or linked list). It involved dividing the input into 2 halves at each step until input has only 1 element and then merging these sorted halves to finally get a sorted input.

Merge sort is not an in-place algorithm (which means you NEED to use extra SPACE for sorting the input).
Merge sort is a stable algorithm which means if there are 2 same elements in the input, the sorted output will maintain the relative ordering of these elements.

Time Complexity: O(NLogN) even in the WORST case. (where N is the size of the input)
Space Complexity: O(N)

Discussion

No Comment Found

Related InterviewSolutions

SQL Query to find min, max and average salary from a table?
Difference between List and Tuple in Python?
Advantages of a vector over an array in C++?
What is the size of empty class in C++?
Write a python program to filter list elements between 1 to 20 (both inclusive) which are even numbers?
What will be the output of the below python program?
There are 9 coins and a weighing balance. 8 coins are of the same weight and 1 coin is heavier. In how many minimum numbers of iterations can you find out the heaviest coin in the worst case?
What is Bootstrap? What are the advantages of Bootstrap over CSS?
Print 1-100 without using loops?
What is the output of the following code: