Page 228 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

The MergeSort procedure splits recursively the lists into two smaller sub-lists. The merge Notes
procedure is putting back together the sub-lists, and at the same time it sorts the lists in proper
order, just like in the example from above.
Merge sort guarantees O(n*log(n)) complexity because it always splits the work in half. In order
to understand how we derive this time complexity for merge sort, consider the two factors
involved: the number of recursive calls, and the time taken to merge each list together.

Advantages and Disadvantages of Merge Sort

Advantages of Merge sort are:
is stable

It can be applied to files of any size
Reading through each run during merging and writing the sorted record is also sequential.
The only seeking necessary is as we switch from run to run.
Disadvantages of Merge Sort are:

it requires an extra array;
is recursive;
Thus, we can say that merge sort is a stable algorithm that performs even faster than heap sort
on large data sets. Also, due to use of divide-and-conquer method merge sort parallelises well.
The only drawback could be the use of recursion, which could give some restrictions to limited
memory machines.

Self Assessment

Fill in the blanks:
5. Merge sort is based on ......................... method.
6. The ............................ procedure splits recursively the lists into two smaller sub-lists.

13.4 Radix Sort

Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by
grouping keys by the individual digits which share the same significant position and value.
Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.
Radix sort is a sorting algorithm that sorts the data, integers for example, by splitting the
numbers into individual digits and comparing the individual digits sharing the same significant
position.
Also, a positional notation is required, because instead of integers there could be strings of
characters or floating point numbers.
The radix sort can be classified into 2 types: LSD (least significant digit) or MSD (most significant
digit). The LSD sorting type begins from the least significant digit to the most significant digit
and the MSD works the other way around.

!

Caution Having the number 150, the number 0 is the least significant digit and 1 is the most
significant digit.

LOVELY PROFESSIONAL UNIVERSITY 221