# Module Sort

A collection of useful functions for sorting and comparing characters, strings, and lists.

Author: Michael Hanus

Version: April 2016

## Summary of exported operations:

 ```sort :: Ord a => [a] -> [a]```    The default sorting operation, mergeSort, with standard ordering `<=`. ```sortBy :: (a -> a -> Bool) -> [a] -> [a]```    The default sorting operation: mergeSort ```sorted :: Ord a => [a] -> Bool```    `sorted xs` is satisfied if the elements `xs` are in ascending order. ```sortedBy :: (a -> a -> Bool) -> [a] -> Bool```    `sortedBy leq xs` is satisfied if all adjacent elements of the list `xs` satisfy the ordering predicate `leq`. ```permSort :: Ord a => [a] -> [a]```    Permutation sort with standard ordering `<=`. ```permSortBy :: Eq a => (a -> a -> Bool) -> [a] -> [a]```    Permutation sort with ordering as first parameter. ```insertionSort :: Ord a => [a] -> [a]```    Insertion sort with standard ordering `<=`. ```insertionSortBy :: (a -> a -> Bool) -> [a] -> [a]```    Insertion sort with ordering as first parameter. ```quickSort :: Ord a => [a] -> [a]```    Quicksort with standard ordering `<=`. ```quickSortBy :: (a -> a -> Bool) -> [a] -> [a]```    Quicksort with ordering as first parameter. ```mergeSort :: Ord a => [a] -> [a]```    Bottom-up mergesort with standard ordering `<=`. ```mergeSortBy :: (a -> a -> Bool) -> [a] -> [a]```    Bottom-up mergesort with ordering as first parameter. ```leqList :: Eq a => (a -> a -> Bool) -> [a] -> [a] -> Bool```    Less-or-equal on lists. ```cmpList :: (a -> a -> Ordering) -> [a] -> [a] -> Ordering```    Comparison of lists. ```leqChar :: Char -> Char -> Bool```    Less-or-equal on characters (deprecated, use `Prelude.<=`). ```cmpChar :: Char -> Char -> Ordering```    Comparison of characters (deprecated, use `Prelude.compare`). ```leqCharIgnoreCase :: Char -> Char -> Bool```    Less-or-equal on characters ignoring case considerations. ```leqString :: String -> String -> Bool```    Less-or-equal on strings (deprecated, use `Prelude.<=`). ```cmpString :: String -> String -> Ordering```    Comparison of strings (deprecated, use `Prelude.compare`). ```leqStringIgnoreCase :: String -> String -> Bool```    Less-or-equal on strings ignoring case considerations. ```leqLexGerman :: String -> String -> Bool```    Lexicographical ordering on German strings.

## Exported operations:

 ```sort :: Ord a => [a] -> [a]```    The default sorting operation, mergeSort, with standard ordering `<=`. Postcondition: `ys = sort xs` satisfies ``` (length xs == length ys) && sorted ys``` (sort'post) Specification: `(sort xs)` is equivalent to ``` permSort xs``` (sort'spec)
 ```sortBy :: (a -> a -> Bool) -> [a] -> [a]```    The default sorting operation: mergeSort
 ```sorted :: Ord a => [a] -> Bool```    `sorted xs` is satisfied if the elements `xs` are in ascending order.
 ```sortedBy :: (a -> a -> Bool) -> [a] -> Bool```    `sortedBy leq xs` is satisfied if all adjacent elements of the list `xs` satisfy the ordering predicate `leq`.
 ```permSort :: Ord a => [a] -> [a]```    Permutation sort with standard ordering `<=`. Sorts a list by finding a sorted permutation of the input. This is not a usable way to sort a list but it can be used as a specification of other sorting algorithms.
 ```permSortBy :: Eq a => (a -> a -> Bool) -> [a] -> [a]```    Permutation sort with ordering as first parameter. Sorts a list by finding a sorted permutation of the input. This is not a usable way to sort a list but it can be used as a specification of other sorting algorithms.
 ```insertionSort :: Ord a => [a] -> [a]```    Insertion sort with standard ordering `<=`. The list is sorted by repeated sorted insertion of the elements into the already sorted part of the list. Postcondition: `ys = insertionSort xs` satisfies ``` (length xs == length ys) && sorted ys``` (insertionSort'post) Specification: `(insertionSort x1)` is equivalent to ``` permSort x1``` (insertionSort'spec)
 ```insertionSortBy :: (a -> a -> Bool) -> [a] -> [a]```    Insertion sort with ordering as first parameter. The list is sorted by repeated sorted insertion of the elements into the already sorted part of the list.
 ```quickSort :: Ord a => [a] -> [a]```    Quicksort with standard ordering `<=`. The classical quicksort algorithm on lists. Postcondition: `ys = quickSort xs` satisfies ``` (length xs == length ys) && sorted ys``` (quickSort'post) Specification: `(quickSort x1)` is equivalent to ``` permSort x1``` (quickSort'spec)
 ```quickSortBy :: (a -> a -> Bool) -> [a] -> [a]```    Quicksort with ordering as first parameter. The classical quicksort algorithm on lists.
 ```mergeSort :: Ord a => [a] -> [a]```    Bottom-up mergesort with standard ordering `<=`. Postcondition: `ys = mergeSort xs` satisfies ``` (length xs == length ys) && sorted ys``` (mergeSort'post) Specification: `(mergeSort x1)` is equivalent to ``` permSort x1``` (mergeSort'spec)
 ```mergeSortBy :: (a -> a -> Bool) -> [a] -> [a]```    Bottom-up mergesort with ordering as first parameter.
 ```leqList :: Eq a => (a -> a -> Bool) -> [a] -> [a] -> Bool```    Less-or-equal on lists.
 ```cmpList :: (a -> a -> Ordering) -> [a] -> [a] -> Ordering```    Comparison of lists.
 ```leqChar :: Char -> Char -> Bool```    Less-or-equal on characters (deprecated, use `Prelude.<=`).
 ```cmpChar :: Char -> Char -> Ordering```    Comparison of characters (deprecated, use `Prelude.compare`).
 ```leqCharIgnoreCase :: Char -> Char -> Bool```    Less-or-equal on characters ignoring case considerations.
 ```leqString :: String -> String -> Bool```    Less-or-equal on strings (deprecated, use `Prelude.<=`).
 ```cmpString :: String -> String -> Ordering```    Comparison of strings (deprecated, use `Prelude.compare`).
 ```leqStringIgnoreCase :: String -> String -> Bool```    Less-or-equal on strings ignoring case considerations.
 ```leqLexGerman :: String -> String -> Bool```    Lexicographical ordering on German strings. Thus, upper/lowercase are not distinguished and Umlauts are sorted as vocals.