# CHAPTER 2

# Mathematical Algorithms

## 2.1 INTRODUCTION

In this chapter, we will introduce a non-exhaustive set of numerical algorithms that play an essential part in the course of pricing programs:

- sorting algorithms
- implicit equation solving
- optimization (search for extrema)
- integration
- linear algebra.

The table below enumerates some of their contributions in quantitative finance:

## 2.2 SORTING LISTS

Data sorting aims at ordering huge amounts of numerical values recorded in financial databases or sampled by Monte-Carlo trials. In this section, we will introduce two popular sorting algorithms, **Shellsort** and **QuickSort**. The reader can refer to Knuth (1998) for more sorting methods.

### 2.2.1 Shell sort

This method was devised by Donald Shell (1959). The basic idea is to partition a large database into smaller subsets and to sort each separately, before sorting the entire set. The sorting method is called the **insertion method**, evoking the way a bridge player orders his deck of cards: it is efficient with rather short lists, or already sorted lists when they are placed end to end.

**Sorting by insertion** This simple algorithm sorts one element of a list at a time. Every element is inserted at the correct position in an already sorted list. We start by sorting the two left-most elements of the list, then insert the third one, and proceed until we obtain the last element.

The VBA procedure ...