QuickSort and MergeSort in JAVA

QuickSort

QuickSort is a very famous sort algorithm, Arrays.sort is realized by QuickSort.

Overview

The basic method is following:
1. Choosing a pivot, always the lowest value.
2. Dividing the array into two parts, the lower part will be put left of the pivot, and the larger part is right.
3. With each round, the pivot will move to the final position in the array.
4. Repeat the process, until the sort is completed.

Code in JAVA

MergeSort

Overview

Conceptually, a merge sort works as follows:

  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Code in JAVA

Analysis

In sorting n objects, merge sort has an average and worst-case performance of O(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists). The closed form follows from the master theorem.

Compare

QuickSort has two major deficiencies when compared to mergesort:

  1. It’s not stable (as parsifal noted).

  2. It doesn’t guarantee n log n performance; it can degrade to quadratic performance on pathological inputs.

and a detailed comparison is following
(From WiKiPedia):

name Best Average Worst Memory Stable
QuickSort nlogn nlogn n^2 logn on average, worst n Typical is no, but stable versions exist
MergeSort nlogn nlogn nlogn n yes

Leave a Reply

Your email address will not be published. Required fields are marked *