Quick Sort Vs Merge Sort

The quick sort and merge sort algorithms are based on the divide and conquer algorithm which works in the quite similar way. The prior difference between the quick and merge sort is that in quick sort the pivot element is used for the sorting. On the other hand, merge sort does not use pivot element for performing the sorting.

 Both sorting techniques, quick sort and merge sort are built on the divide and conquer method in which the set of elements are parted and then combined after rearrangement. The quick sort usually requires more comparisons than merge sort for sorting a large set of elements.

Key Differences Between Quick Sort and Merge Sort :

  1. In the merge sort, the array must be parted into just two halves (i.e. n/2). As against, in quick sort, there is no compulsion of dividing the list into equal elements.
  2. The worst case complexity of quick sort is O(n2) as it takes a lot more comparisons in the worst condition. In contrast, merge sort have the same worst case and average case complexities, that is O(n log n).
  3. Merge sort can operate well on any type of data sets whether it is large or small. On the contrary, the quick sort cannot work well with large datasets.
  4. Quick sort is faster than merge sort in some cases such as for small data sets.
  5. Merge sort requires additional memory space to store the auxiliary arrays. On the other hand, the quick sort doesn’t require much space for extra storage.
  6. Merge sort is more efficient than quick sort.
  7. The quick sort is internal sorting method where the data that is to be sorted is adjusted at a time in main memory. Conversely, the merge sort is external sorting method in which the data that is to be sorted cannot be accommodated in the memory at the same time and some has to be kept in the auxiliary memory.

Conclusion :

The quick sort is faster cases but is inefficient in some situations and also performs a lot of comparisons as compared to merge sort. Although merge sort requires less comparison, it needs an additional memory space of 0(n) for storing the extra array while quick sort needs space of O(log n).

Comments

Post a Comment

Popular posts from this blog

Process Vs Thread

The Process and Thread are the essentially correlated. The process is an execution of a program whereas thread is an execution of a program driven by the environment of a process. Another major point which differentiates process and thread is that processes are isolated with each other whereas threads share memory or resources with each other. Key Differences Between Process and Thread : All threads of a program are logically contained within a process. A process is heavy weighted, but a thread is light weighted. A program is an isolated execution unit whereas thread is not isolated and shares memory. A thread cannot have an individual existence; it is attached to a process. On the other hand, a process can exist individually. Each thread has its own stack, so if a thread dies its stack is reclaimed. In contrast, if a process dies, all threads die including the process. Conclusion: Processes are used to achieve execution of programs in concurrent and sequential manner.
Read more

Reasoning Vs Inference

Inference: Inference is a general term representing the derivation of new knowledge from existing knowledge and axioms (i.e., rules of derivation) within a single step, and can be one of many kinds, such as, induction, deduction and abduction. For example, "modus tollens" is a rule of inference. Thus, one inference is the derivation of new knowledge using a single step using modus tollens. Inference is about taking in data and trying to draw a conclusion based on the limited information you have in a situation where not all the data is given. Reasoning: Reasoning is in context of a goal (e.g., decide whether a propositional formula is satisfiable or not)  and is carried out via a search process involving multiple inferences. Choices during such search have to be made such as which axiom to "fire" along with which knowledge in order to derive new knowledge. Resolution is a particular kind of reasoning involving the "resolution rule". Reasoning is
Read more

Frame vs Packet

Image
Difference Between Frame and Packet     The crucial difference between frame and packet is that frame is the serial collection of bits, and it encapsulates packets whereas packets are the fragmented form of data and it encapsulates segment. Data link layer performs framing process. On the other hand, Network layer performs fragmentation of the data and create smaller chunks known as packets. Another major difference is that a frame includes device’s MAC address while a packet includes device’s IP address. Basis for comparison Frame Packet Basic Frame is the data link layer protocol data unit. Packet is the network layer protocol data unit. Associated OSI layer Data link layer Network layer Includes Source and destination MAC address. Source and destination IP address. Correlation Segment is encapsulated within a packet. Packet is encapsulated within a frame. Conclusion: Frames and Packets function as protocol data units utilized on the
Read more