Sorting

Luong The Nhan

Chapter 10
Sorting Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort
Data Structures and Algorithms Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort
Luong The Nhan
Devide-and-
Faculty of Computer Science and Engineering Conquer
Quick Sort
University of Technology, VNU-HCM Merge Sort

10.1
 Sorting
Outcomes
Luong The Nhan
• L.O.6.1 - Depict the working steps of sorting
algorithms step-by-steps.
• L.O.6.2 - Describe sorting algorithms by using
pseudocode.
• L.O.6.3 - Implement sorting algorithms using C/C++ . Sorting concepts

Insertion Sort
• L.O.6.4 - Analyze the complexity and develop Straight Insertion Sort

experiment (program) to evaluate sorting algorithms. Shell Sort

Selection Sort
• L.O.6.5 - Use sorting algorithms for problems in Straight Selection Sort
Heap Sort
real-life. Exchange Sort
• L.O.8.4 - Develop recursive implementations for Bubble Sort

Devide-and-
methods supplied for the following structures: list, tree, Conquer
heap, searching, and graphs. Quick Sort
Merge Sort

• L.O.1.2 - Analyze algorithms and use Big-O notation to

characterize the computational complexity of algorithms
composed by using the following control structures:
sequence, branching, and iteration (not recursion).
10.2
 Sorting
Contents
Luong The Nhan

1 Sorting concepts

2 Insertion Sort
Straight Insertion Sort
Shell Sort Sorting concepts

Insertion Sort
Straight Insertion Sort
3 Selection Sort Shell Sort

Straight Selection Sort Selection Sort

Straight Selection Sort
Heap Sort Heap Sort

Exchange Sort
4 Exchange Sort Bubble Sort

Devide-and-
Bubble Sort Conquer
Quick Sort
Merge Sort
5 Devide-and-Conquer
Quick Sort
Merge Sort

10.3
 Sorting

Luong The Nhan

Sorting concepts

Insertion Sort

Sorting concepts Straight Insertion Sort

Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.4
 Sorting
Sorting
Luong The Nhan

One of the most important concepts and

common applications in computing.
Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.5
 Sorting
Sorting
Luong The Nhan

Sort stability: data with equal keys maintain

their relative input order in the output.
Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.6
 Sorting
Sorting
Luong The Nhan

Sorting concepts

Sort efficiency: a measure of the relative Insertion Sort

Straight Insertion Sort
Shell Sort

efficiency of a sort = number of comparisons + Selection Sort

number of moves. Straight Selection Sort

Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.7
 Sorting
Sorting
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.8
 Sorting

Luong The Nhan

Sorting concepts

Insertion Sort

Insertion Sort Straight Insertion Sort

Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.9
 Sorting
Straight Insertion Sort
Luong The Nhan

• The list is divided into two parts: sorted

and unsorted.

• In each pass, the first element of the Sorting concepts

Insertion Sort
unsorted sublist is inserted into the sorted Straight Insertion Sort
Shell Sort

sublist. Selection Sort

Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.10
 Sorting
Straight Insertion Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.11
 Sorting
Straight Insertion Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.12
 Sorting
Straight Insertion Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.13
 Sorting
Straight Insertion Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.14
 Sorting
Straight Insertion Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.15
 Sorting
Straight Insertion Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.16
 Sorting
Straight Insertion Sort
Luong The Nhan
Algorithm InsertionSort()
Sorts the contiguous list using straight insertion sort.

if count > 1 then

current = 1
while current < count do Sorting concepts

temp = data[current] Insertion Sort

Straight Insertion Sort

walker = current - 1 Shell Sort

Selection Sort
while walker >= 0 AND temp.key < Straight Selection Sort

data[walker].key do Heap Sort

Exchange Sort
data[walker+1] = data[walker] Bubble Sort

walker = walker - 1 Devide-and-

end Conquer
Quick Sort

data[walker+1] = temp Merge Sort

current = current + 1
end
end
End InsertionSort 10.17
 Sorting
Shell Sort
Luong The Nhan

• Named after its creator Donald L. Shell

(1959).
Sorting concepts
• Given a list of N elements, the list is Insertion Sort

divided into K segments (K is called the Straight Insertion Sort

Shell Sort

increment). Selection Sort

Straight Selection Sort
Heap Sort

• Each segment contains N/K or more Exchange Sort

Bubble Sort

elements. Devide-and-
Conquer
• Segments are dispersed throughout the list. Quick Sort
Merge Sort

• Also is called diminishing-increment sort.

10.18
 Sorting
Shell Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.19
 Sorting
Shell Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
• For the value of K in each iteration, sort Straight Selection Sort
Heap Sort

the K segments. Exchange Sort

Bubble Sort

Devide-and-
• After each iteration, K is reduced until it is Conquer
Quick Sort

1 in the final iteration. Merge Sort

10.20
 Sorting
Example of Shell Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.21
 Sorting
Example of Shell Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.22
 Sorting
Choosing incremental values
Luong The Nhan

• From more of the comparisons, it is better

when we can receive more new information. Sorting concepts

Insertion Sort
Straight Insertion Sort

• Incremental values should not be multiples Shell Sort

Selection Sort
of each other, other wise, the same keys Straight Selection Sort
Heap Sort

compared on one pass would be compared Exchange Sort

Bubble Sort

again at the next. Devide-and-

Conquer
Quick Sort

• The final incremental value must be 1. Merge Sort

10.23
 Sorting
Choosing incremental values
Luong The Nhan

• Incremental values may be:

1, 4, 13, 40, 121, ...
kt = 1 Sorting concepts

ki−1 = 3 ∗ ki + 1 Insertion Sort

Straight Insertion Sort

t = | log3 n| − 1 Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

• or: Exchange Sort

Bubble Sort

1, 3, 7, 15, 31, ... Devide-and-

Conquer
kt = 1 Quick Sort
Merge Sort

ki−1 = 2 ∗ ki + 1
t = | log2 n| − 1

10.24
 Sorting
Shell Sort
Luong The Nhan

Algorithm ShellSort()
Sorts the contiguous list using Shell sort.

k = first_incremental_value Sorting concepts

while k >= 1 do Insertion Sort

Straight Insertion Sort

segment = 1 Shell Sort

Selection Sort
while segment <= k do Straight Selection Sort
Heap Sort

SortSegment(segment) Exchange Sort

Bubble Sort

segment = segment + 1 Devide-and-

end Conquer
Quick Sort
Merge Sort

k = next_incremental_value
end
End ShellSort
10.25
 Sorting
Shell Sort
Algorithm SortSegment(val segment <int>, val k Luong The Nhan

<int>)
Sorts the segment beginning at segment using insertion
sort, step between elements in the segment is k.

current = segment + k Sorting concepts

Insertion Sort
while current < count do Straight Insertion Sort

temp = data[current] Shell Sort

Selection Sort
walker = current - k Straight Selection Sort

while walker >=0 AND temp.key < Heap Sort

Exchange Sort
data[walker].key do Bubble Sort

data[walker + k] = data[walker] Devide-and-

Conquer
walker = walker - k Quick Sort

end Merge Sort

data[walker + k] = temp
current = current + k
end
End SortSegment
10.26
 Sorting
Insertion Sort Efficiency
Luong The Nhan

• Straight insertion sort: Sorting concepts

Insertion Sort
f (n) = n(n + 1)/2 = O(n2 ) Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
• Shell sort: Heap Sort

O(n1.25 ) (Empirical study) Exchange Sort

Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.27
 Sorting

Luong The Nhan

Sorting concepts

Insertion Sort

Selection Sort Straight Insertion Sort

Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.28
 Sorting
Selection Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort
In each pass, the smallest/largest item is Selection Sort

selected and placed in a sorted list. Straight Selection Sort

Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.29
 Sorting
Straight Selection Sort
Luong The Nhan

• The list is divided into two parts: sorted

and unsorted.

• In each pass, in the unsorted sublist, the Sorting concepts

Insertion Sort
smallest element is selected and exchanged Straight Insertion Sort
Shell Sort

with the first element. Selection Sort

Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.30
 Sorting
Straight Selection Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.31
 Sorting
Straight Selection Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.32
 Sorting
Straight Selection Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.33
 Sorting
Straight Selection Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.34
 Sorting
Straight Selection Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.35
 Sorting
Straight Selection Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.36
 Sorting
Straight Selection Sort
Luong The Nhan
Algorithm SelectionSort()
Sorts the contiguous list using straight selection sort.

current = 0
while current < count - 1 do Sorting concepts
smallest = current Insertion Sort
walker = current + 1 Straight Insertion Sort
Shell Sort

while walker < count do Selection Sort

if data [walker].key < data [smallest].key then Straight Selection Sort
Heap Sort

smallest = walker Exchange Sort

end Bubble Sort

Devide-and-
walker = walker + 1 Conquer
end Quick Sort
Merge Sort

swap(current, smallest)
current = current + 1
end
End SelectionSort
10.37
 Sorting
Heap Sort
Luong The Nhan

• The unsorted sublist is organized into a

heap.

• In each pass, in the unsorted sublist, the Sorting concepts

largest element is selected and exchanged Insertion Sort

Straight Insertion Sort

with the last element. Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

• The the heap is reheaped. Exchange Sort

Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.38
 Sorting
Heap Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.39
 Sorting
Heap Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.40
 Sorting
Heap Sort
Luong The Nhan

Algorithm HeapSort()
Sorts the contiguous list using heap sort.

position = count/2 - 1
Sorting concepts
while position >= 0 do
Insertion Sort
ReheapDown(position, count - 1) Straight Insertion Sort

position = position - 1 Shell Sort

Selection Sort
end Straight Selection Sort

last = count - 1 Heap Sort

Exchange Sort
while last > 0 do Bubble Sort

swap(0, last) Devide-and-

Conquer
last = last - 1 Quick Sort

ReheapDown(0, last - 1) Merge Sort

end
End HeapSort

10.41
 Sorting
Selection Sort Efficiency
Luong The Nhan

• Straight selection sort: Sorting concepts

Insertion Sort
O(n2 ) Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
• Heap sort: Heap Sort

Exchange Sort
O(nlog2 n) Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.42
 Sorting

Luong The Nhan

Sorting concepts

Insertion Sort

Exchange Sort Straight Insertion Sort

Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.43
 Sorting
Exchange Sort
Luong The Nhan

Sorting concepts

• In each pass, elements that are out of order Insertion Sort

Straight Insertion Sort

are exchanged, until the entire list is sorted. Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort
• Exchange is extensively used. Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.44
 Sorting
Bubble Sort
Luong The Nhan

• The list is divided into two parts: sorted

and unsorted.

• In each pass, the smallest element is Sorting concepts

Insertion Sort
bubbled from the unsorted sublist and Straight Insertion Sort
Shell Sort

moved to the sorted sublist. Selection Sort

Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.45
 Sorting
Bubble Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.46
 Sorting
Bubble Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.47
 Sorting
Bubble Sort
Luong The Nhan
Algorithm BubbleSort()
Sorts the contiguous list using bubble sort.

current = 0
flag = False
Sorting concepts
while current < count AND flag = False do
Insertion Sort
walker = count - 1 Straight Insertion Sort

flag = True Shell Sort

Selection Sort
while walker > current do Straight Selection Sort

if data [walker].key < data [walker-1].key then Heap Sort

Exchange Sort
flag = False Bubble Sort

swap(walker, walker - 1) Devide-and-

Conquer
end Quick Sort

walker = walker - 1 Merge Sort

end
current = current + 1
end
End BubbleSort 10.48
 Sorting
Exchange Sort Efficiency
Luong The Nhan

Sorting concepts

Insertion Sort

• Bubble sort: Straight Insertion Sort

Shell Sort

f (n) = n(n + 1)/2 = O(n2 ) Selection Sort

Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.49
 Sorting

Luong The Nhan

Sorting concepts

Insertion Sort

Devide-and-Conquer Straight Insertion Sort

Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.50
 Sorting
Devide-and-Conquer Sort
Luong The Nhan

Algorithm DevideAndConquer()
if the list has length > 1 then Sorting concepts

partition the list into lowlist and highlist Insertion Sort

Straight Insertion Sort

lowlist.DevideAndConquer() Shell Sort

Selection Sort
highlist.DevideAndConquer() Straight Selection Sort
Heap Sort

combine(lowlist, highlist) Exchange Sort

Bubble Sort

end Devide-and-
Conquer
End DevideAndConquer Quick Sort
Merge Sort

10.51
 Sorting
Devide-and-Conquer Sort
Luong The Nhan

Sorting concepts

Partition Combine Insertion Sort

Straight Insertion Sort

Merge Sort easy hard Shell Sort

Selection Sort
Quick Sort hard easy Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.52
 Sorting
Quick Sort
Luong The Nhan

Algorithm QuickSort() Sorting concepts

Insertion Sort
Sorts the contiguous list using quick sort. Straight Insertion Sort
Shell Sort

Selection Sort

recursiveQuickSort(0, count - 1) Straight Selection Sort

Heap Sort

End QuickSort Exchange Sort

Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.53
 Sorting
Quick Sort
Algorithm recursiveQuickSort(val left <int>, Luong The Nhan

val right <int>)

Sorts the contiguous list using quick sort.
Pre: left and right are valid positions in the
Sorting concepts
list Insertion Sort

Post: list sorted

Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort

if left < right then Heap Sort

Exchange Sort
pivot_position = Partition(left, right) Bubble Sort

Devide-and-
recursiveQuickSort(left, pivot_position - 1) Conquer
Quick Sort

recursiveQuickSort(pivot_position + 1, Merge Sort

right)
end
End recursiveQuickSort 10.54
 Sorting
Quick Sort
Luong The Nhan

Given a pivot value, the partition rearranges

Sorting concepts
the entries in the list as the following figure: Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.55
 Sorting
Quick Sort Efficiency
Luong The Nhan

Sorting concepts

Insertion Sort

• Quick sort: Straight Insertion Sort

Shell Sort

O(nlog2 n) Selection Sort

Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.56
 Sorting
Merge Sort
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.57
 Sorting
Merge Sort
Luong The Nhan

Algorithm MergeSort() Sorting concepts

Insertion Sort
Sorts the linked list using merge sort. Straight Insertion Sort
Shell Sort

Selection Sort
recursiveMergeSort(head) Straight Selection Sort
Heap Sort

End MergeSort Exchange Sort

Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.58
 Sorting
Merge Sort
Luong The Nhan

Algorithm recursiveMergeSort(ref sublist

<pointer>)
Sorts the linked list using recursive merge sort.
Sorting concepts

Insertion Sort
if sublist is not NULL AND sublist->link is not Straight Insertion Sort
Shell Sort

NULL then Selection Sort

Divide(sublist, second_list) Straight Selection Sort

Heap Sort

recursiveMergeSort(sublist) Exchange Sort

Bubble Sort

recursiveMergeSort(second_list) Devide-and-
Conquer

Merge(sublist, second_list) Quick Sort

Merge Sort

end
End recursiveMergeSort
10.59
 Sorting
Merge Sort
Luong The Nhan

Algorithm Divide(val sublist <pointer>, ref second_list

<pointer>)
Divides the list into two halves.

midpoint = sublist Sorting concepts

position = sublist->link Insertion Sort

Straight Insertion Sort
while position is not NULL do Shell Sort

position = position->link Selection Sort

Straight Selection Sort
if position is not NULL then Heap Sort

midpoint = midpoint->link Exchange Sort

Bubble Sort
position = position->link Devide-and-
end Conquer
Quick Sort

end Merge Sort

second_list = midpoint->link
midpoint->link = NULL
End Divide
10.60
 Sorting
Merge two sublists
Luong The Nhan

Sorting concepts

Insertion Sort
Straight Insertion Sort
Shell Sort

Selection Sort
Straight Selection Sort
Heap Sort

Exchange Sort
Bubble Sort

Devide-and-
Conquer
Quick Sort
Merge Sort

10.61
 Sorting
Merge two sublists
Luong The Nhan
Algorithm Merge(ref first <pointer>, ref second
<pointer>)
Merges two sorted lists into a sorted list.

lastSorted = address of combined

Sorting concepts
while first is not NULL AND second is not NULL do
Insertion Sort
if first->data.key <= second->data.key then Straight Insertion Sort

lastSorted->link = first Shell Sort

Selection Sort
lastSorted = first Straight Selection Sort

first = first->link Heap Sort

else Exchange Sort

Bubble Sort

lastSorted->link = second Devide-and-

lastSorted = second Conquer
Quick Sort

second = second->link Merge Sort

end
end

// ...
10.62
 Sorting
Merge two sublists
Luong The Nhan

// ...

if first is NULL then Sorting concepts

lastSorted->link = second Insertion Sort

Straight Insertion Sort

second = NULL Shell Sort

Selection Sort
else Straight Selection Sort
Heap Sort

lastSorted->link = first Exchange Sort

end
Bubble Sort

Devide-and-

first = combined.link Conquer

Quick Sort
Merge Sort

End Merge

10.63