text:
Smoothsort

In computer science, smoothsort is a comparison-based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of $O(n log n)$ operations (see big O notation), but it is not a stable sort. The advantage of smoothsort is that it comes closer to $O(n)$ time if the input is already sorted to some degree, whereas heapsort averages $O(n log n)$ regardless of the initial sorted state.

Overview
Like heapsort, smoothsort organizes the input into a priority queue and then repeatedly extracts the maximum. Also like heapsort, the priority queue is an implicit heap data structure (a heap-ordered implicit binary tree), which occupies a prefix of the array. Each extraction shrinks the prefix and adds the extracted element to a growing sorted suffix. When the prefix has shrunk to nothing, the array is completely sorted.

Heapsort maps the binary tree to the array using a top-down breadth-first traversal of the tree; the array begins with the root of the tree, then its two children, then four grandchildren, and so on. Every element has a well-defined depth below the root of the tree, and every element except the root has its parent earlier in the array. Its height above the leaves, however, depends on the size of the array. This has the disadvantage that every element must be moved as part of the sorting process: it must pass through the root before being moved to its final location.

Smoothsort uses a different mapping, a bottom-up depth-first post-order traversal. A left child is followed by the subtree rooted at its sibling, and a right child is followed by its parent. Every element has a well-defined height above the leaves, and every non-leaf element has its children earlier in the array. Its depth below the root, however, depends on the size of the array. The algorithm is organized so the root is at the end of the heap, and at the moment that an element is extracted from the heap it is already in its final location and does not need to be moved. Also, a sorted array is already a valid heap, and many sorted intervals are valid heap-ordered subtrees.

More formally, every position $i$ is the root of a unique subtree, whose nodes occupy a contiguous interval that ends at $i$. An initial prefix of the array (including the whole array), might be such an interval corresponding to a subtree, but in general decomposes as a union of a number of successive such subtree intervals, which Dijkstra calls "stretches". Any subtree without a parent (i.e. rooted at a position whose parent lies beyond the prefix under consideration) gives a stretch in the decomposition of that interval, which decomposition is therefore unique. When a new node is appended to the prefix, one of two cases occurs: either the position is a leaf and adds a stretch of length 1 to the decomposition, or it combines with the last two stretches, becoming the parent of their respective roots, thus replacing the two stretches by a new stretch containing their union plus the new (root) position.

Dijkstra noted that the obvious rule would be to combine stretches if and only if they have equal size, in which case all subtrees would be perfect binary trees of size $O(n)$. However, he chose a different rule, which gives more possible tree sizes. This has the same asymptotic efficiency, but gains a small constant factor in efficiency by requiring fewer stretches to cover each interval.

The rule Dijkstra uses is that the last two stretches are combined if and only if their sizes are consecutive Leonardo numbers $O(1)$ and $O(n log n)$ (in that order), which numbers are recursively defined, in a manner very similar to the Fibonacci numbers, as: As a consequence, the size of any subtree is a Leonardo number. The sequence of stretch sizes decomposing the first $n$ positions, for any $n$, can be found in a greedy manner: the first size is the largest Leonardo number not exceeding $n$, and the remainder (if any) is decomposed recursively. The sizes of stretches are decreasing, strictly so except possibly for two final sizes 1, and avoiding successive Leonardo numbers except possibly for the final two sizes.

In addition to each stretch being a heap-ordered tree, the roots of the trees are maintained in sorted order. This effectively adds a third child (which Dijkstra calls a "stepson") to each root linking it to the preceding root. This combines all of the trees together into one global heap. with the global maximum at the end.

Although the location of each node's stepson is fixed, the link only exists for tree roots, meaning that links are removed whenever trees are merged. This is different from ordinary children, which are linked as long as the parent exists.

In the first (heap growing) phase of sorting, an increasingly large initial part of the array is reorganized so that the subtree for each of its stretches is a max-heap: the entry at any non-leaf position is at least as large as the entries at the positions that are its children. In addition, all roots are at least as large as their stepsons.

In the second (heap shrinking) phase, the maximal node is detached from the end of the array (without needing to move it) and the heap invariants are re-established among its children. (Specifically, among the newly created stepsons.)

Practical implementation frequently needs to compute Leonardo numbers $O(n)$. Dijkstra provides clever code which uses a fixed number of integer variables to efficiently compute the values needed at the time they are needed. Alternatively, if there is a finite bound $N$ on the size of arrays to be sorted, a precomputed table of Leonardo numbers can be stored in $O(n log n)$ space.

Operations
While the two phases of the sorting procedure are opposite to each other as far as the evolution of the sequence-of-heaps structure is concerned, they are implemented using one core primitive, equivalent to the "sift down" operation in a binary max-heap.

Sifting down
The core sift-down operation (which Dijkstra calls "trinkle") restores the heap invariant when it is possibly violated only at the root node. If the root node is less than any of its children, it is swapped with its greatest child and the process repeated with the root node in its new subtree.

The difference between smoothsort and a binary max-heap is that the root of each stretch must be ordered with respect to a third "stepson": the root of the preceding stretch. So the sift-down procedure starts with a series of four-way comparisons (the root node and three children) until the stepson is not the maximal element, then a series of three-way comparisons (the root plus two children) until the root node finds its final home and the invariants are re-established.

Each tree is a full binary tree: each node has two children or none. There is no need to deal with the special case of one child which occurs in a standard implicit binary heap. (But the special case of stepson links more than makes up for this saving.)

Because there are $2^{k}−1$ stretches, each of which is a tree of depth $L(i+1)$, the time to perform each sifting-down operation is bounded by $L(i)$.

Growing the heap region by incorporating an element to the right
When an additional element is considered for incorporation into the sequence of stretches (list of disjoint heap structures) it either forms a new one-element stretch, or it combines the two rightmost stretches by becoming the parent of both their roots and forming a new stretch that replaces the two in the sequence. Which of the two happens depends only on the sizes of the stretches currently present (and ultimately only on the index of the element added); Dijkstra stipulated that stretches are combined if and only if their sizes are $L(0) = L(1) = 1$ and $L(k+2) = L(k+1) + L(k) + 1$ for some $k$, i.e., consecutive Leonardo numbers; the new stretch will have size $L(k)$.

In either case, the new element must be sifted down to its correct place in the heap structure. Even if the new node is a one-element stretch, it must still be sorted relative to the preceding stretch's root.

Optimization
Dijkstra's algorithm saves work by observing that the full heap invariant is required at the end of the growing phase, but it is not required at every intermediate step. In particular, the requirement that an element be greater than its stepson is only important for the elements which are the final tree roots.

Therefore, when an element is added, compute the position of its future parent. If this is within the range of remaining values to be sorted, act as if there is no stepson and only sift down within the current tree.

Shrinking the heap region by separating the rightmost element from it
During this phase, the form of the sequence of stretches goes through the changes of the growing phase in reverse. No work at all is needed when separating off a leaf node, but for a non-leaf node its two children become roots of new stretches, and need to be moved to their proper place in the sequence of roots of stretches. This can be obtained by applying sift-down twice: first for the left child, and then for the right child (whose stepson was the left child).

Because half of all nodes in a full binary tree are leaves, this performs an average of one sift-down operation per node.

Optimization
It is already known that the newly exposed roots are correctly ordered with respect to their normal children; it is only the ordering relative to their stepsons which is in question. Therefore, while shrinking the heap, the first step of sifting down can be simplified to a single comparison with the stepson. If a swap occurs, subsequent steps must do the full four-way comparison.

Analysis
Smoothsort takes $O(log N)$ time to process a presorted array, $O(log n)$ in the worst case, and achieves nearly linear performance on many nearly sorted inputs. However, it does not handle all nearly sorted sequences optimally. Using the count of inversions as a measure of un-sortedness (the number of pairs of indices $i$ and $j$ with $O(log n)$ and $O(log n)$; for randomly sorted input this is approximately $L(k+1)$), there are possible input sequences with $L(k)$ inversions which cause it to take $L(k+2)$ time, whereas other adaptive sorting algorithms can solve these cases in $O(n)$ time.

The smoothsort algorithm needs to be able to hold in memory the sizes of all of the trees in the Leonardo heap. Since they are sorted by order and all orders are distinct, this is usually done using a bit vector indicating which orders are present. Moreover, since the largest order is at most $O(n log n)$, these bits can be encoded in $i < j$ machine words, assuming a transdichotomous machine model.

Note that $A[i] > A[j]$ machine words is not the same thing as one machine word. A 32-bit vector would only suffice for sizes less than $n^{2}/4$. A 64-bit vector will do for sizes less than $O(n log n)$. In general, it takes $Ω(n log n)$ bits of vector per bit of size.

Poplar sort
A simpler algorithm inspired by smoothsort is poplar sort. Named after the rows of trees of decreasing size often seen in Dutch polders, it performs fewer comparisons than smoothsort for inputs that are not mostly sorted, but cannot achieve linear time for sorted inputs.

The significant change made by poplar sort in that the roots of the various trees are not kept in sorted order; there are no "stepson" links tying them together into a single heap. Instead, each time the heap is shrunk in the second phase, the roots are searched to find the maximum entry.

Because there are $n$ shrinking steps, each of which must search $O(n log log n)$ tree roots for the maximum, the best-case run time for poplar sort is $O(log n)$.

The authors also suggest using perfect binary trees rather than Leonardo trees to provide further simplification, but this is a less significant change.

The same structure has been proposed as a general-purpose priority queue under the name post-order heap, achieving $O(1)$ amortized insertion time in a structure simpler than an implicit binomial heap.

Applications
The musl C library uses smoothsort for its implementation of.

title: Smoothsort


text:
The Wash

The Wash is a shallow natural rectangular bay and multiple estuary on the east coast of England, United Kingdom. The bay is an inlet of the North Sea. It is the largest estuary system in the United Kingdom, the largest natural bay in England and one of the most important places of conservation in Europe, with several nature reserves.

The coastline is partly in Lincolnshire and partly in Norfolk. The Norfolk part forms the north-west corner of East Anglia. The coastline stretches from Gibraltar Point near Skegness in Lincolnshire to Gore Point near the village of Holme-next-the-Sea in Norfolk. These two points are over 75 mi from each other by road, but only 11+1/2 mi by sea.

The bay is made up of multiple estuaries, marshland, deep water channels (in particular the Boston and Lynn Deeps), shifting shallow water channels which are all surrounded by multiple sandbanks.

There are several large settlements near its coastline, the largest is the town of King's Lynn in Norfolk followed by the two slightly smaller towns of Boston in Lincolnshire and Wisbech in Cambridgeshire. These are the three main inland ports in the Wash area; another port is the Lincolnshire village of Sutton Bridge. Nearby, on either side of the Wash, are the seaside towns of Hunstanton and Skegness. Also nearby is the royal estate of Sandringham.

Geography
The Wash makes a large indentation in the coastline of Eastern England that separates Lincolnshire from the curved coast of East Anglia. It is a large bay with three roughly straight sides meeting at right angles, each about 15 mi in length.

The western coast, which is roughly parallel to the east coast, runs from Gibraltar Point to the mouth of the River Welland just north east of the village of Fosdyke, and is entirely within Lincolnshire. The southern coast from Fosdyke to King's Lynn runs roughly north-west to south-east, connecting these two river mouths, and is punctuated by the mouth of a third river, the River Nene, which flows into the Wash just north of Sutton Bridge with the county boundary between Lincolnshire and Norfolk (which is also the regional boundary between the East Midlands and the East of England) meeting just beyond this point before it continues eastwards to Ongar Hill where it meets the mouth of the River Great Ouse.

The eastern coast of the Wash is entirely within Norfolk, and initially extends from the mouth of the River Great Ouse just north of the town of King's Lynn north eastwards towards the small village of Wolferton close to the Sandringham estate before heading northwards from Snettisham to the low lands of Heacham, the town of Hunstanton, and the village of Old Hunstanton, before reaching its northern extremity at Gore Point near Holme-next-the-Sea, where the Norfolk coast turns eastwards.

Inland from the Wash the land is flat, low-lying and often marshy: these are the Fens of Lincolnshire, Cambridgeshire and Norfolk.

Deposits of sediment and land reclamation have altered the coastline of the Wash markedly in historical times. Several towns once on the coast of the Wash (notably King's Lynn) are now some distance inland. Much of the Wash itself is very shallow, with several large sandbanks, such as Breast Sand, Bulldog Sand, Roger Sand and Old South Sand, which are exposed at low tide, especially along the south coast. These form hazards to navigation.

Three commercial shipping lane channels lead inland from the Wash:
 * the River Nene leading to Port Sutton Bridge in Lincolnshire and further inland to the Port of Wisbech in Cambridgeshire,
 * the River Great Ouse leading to King's Lynn Docks in Norfolk,

both via the large channel known as the Lynn Deeps.
 * The third shipping lane can accessed via the narrower Boston Deeps channel to lead inland, via The Haven (River Witham) to the Port of Boston.

Each of the three shipping lanes has maritime pilot stations to guide and navigate incoming and outgoing cargo ships. Large boats can now only access the River Welland as far as Fosdyke Bridge since the replacement of the old swing bridge which carries the A17 road over the river with a fixed bridge in 1990 following the decline of Spalding as a port during the first part of the 20th century leaving only very small craft being able to use this route.

A re-survey of the coastline of the Wash carried out by the Ordnance Survey in 2011 revealed that an estimated additional 3000 acres on its coastline had been created by accretion since previous surveys between 1960 and 1980.

Water temperature
The Wash varies enormously in water temperature throughout the year. Winter temperatures are brought near freezing by the cold North Sea flows. Summer water temperatures can reach 20 - 23 C after prolonged high ambient air temperature and sun. This effect, which typically happens in the shallow areas around beaches and often only in pockets of water, is exaggerated by the large sheltered tidal reach.

Wildlife
The Wash is made up of extensive salt marshes, major inter-tidal banks of sand and mud, shallow waters and deep channels. As understanding of the importance of the natural marshes has increased in the 21st century, the seawall at Freiston has been breached in three places to increase the salt-marsh area and provide extra habitat for birds, particularly waders, and as a natural flood-prevention measure. The extensive creeks in the salt marsh and the vegetation that grows there help to dissipate wave energy, so enhancing the protection afforded to land behind the salt marsh. This is an example of the recent exploration of the possibilities of sustainable coastal management by adopting soft engineering techniques, rather than with dykes and drainage. The same scheme includes new brackish lagoon habitat.

On the eastern side of the Wash, low chalk cliffs, with a noted stratum of red chalk, are found at Hunstanton. The gravel pits (lagoons) found at Snettisham RSPB reserve are an important roost for waders at high tide. This Special Protection Area (SPA) borders onto the North Norfolk Coast Special Protection Area. To the north-west, the Wash extends to Gibraltar Point, another SPA.

The partly confined nature of the Wash habitats, combined with ample tidal flows, allows shellfish to breed, especially shrimp, cockles and mussels. Some water birds such as oystercatchers feed on shellfish. It is also a breeding area for common tern, and a feeding area for marsh harriers. Migrating birds such as geese, duck and wading birds come to the Wash in large numbers to spend the winter, with an average total of around 400,000 birds present at any one time. It has been estimated that some two million birds a year use the Wash for feeding and roosting during their annual migrations.

The Wash is recognised as being internationally important for 17 species of bird. They include pink-footed goose, dark-bellied brent goose, shelduck, pintail, oystercatcher, ringed plover, grey plover, golden plover, lapwing, knot, sanderling, dunlin, black-tailed godwit, bar-tailed godwit, curlew, redshank and turnstone.

Wash River
At the end of the latest glaciation, and while the sea level remained lower than it is today, the rivers Witham, Welland, Glen, Nene and Great Ouse joined into a large river.

The deep valley of the Wash was formed, not by an interglacial river, but by ice of the Wolstonian and Devensian stages flowing southwards up the slope represented by the modern coast and forming tunnel valleys, of which the Silver Pit is one of many. This process gave the Silver Pit its depth and narrowness. When the tunnel valley was free of ice and seawater, it was occupied by the river. This kept it free of sediment, unlike most tunnel valleys. Since the sea flooded it, the valley seems to have been kept open by tidal action. During the Ipswichian Stage, the Wash River probably flowed by way of the site of the Silver Pit, but the tunnel valley would not have been formed at this stage, as its alignment seems inconsistent.

In Roman Britain, embankments were built around the Wash's margins to protect agricultural land from flooding. However, they fell into disrepair after the Roman withdrawal in 407 CE.

From 865 to about 1066, the Wash was used by the Vikings as a major route to invade East Anglia and Middle England. Danes established themselves in Cambridge in 875. Before the 12th century, when drainage and embankment efforts led by monks began to separate the land from the estuarine mudflats, the Wash was a tidal part of the Fens that reached as far as Cambridge and Peterborough.

Local people put up fierce resistance against the Normans for some time after the 1066 Conquest.

The name Wash may have been derived from Old English wāse meaning mud, slime or ooze. The word Wasche is mentioned in the popular dictionary Promptorium parvulorum of about 1440 as a water or a ford (vadum). A chronicle states that King Edward VI passed the Wasshes as he visited the town of King's Lynn in 1548. By then, documents began to refer to the Waashe or Wysche, but only for the tidal sands and shoals of the rivers Welland and Nene. Sixteenth-century scholars identified the Wash as the Æstuarium Metuonis ("The Reaping/Mowing/Cutting-Off Estuary") mentioned by Ptolemy in Roman times. They claimed the word was still in occasional use. William Camden characterized The Washes as "a very large arme" of the "German Ocean" (the North Sea), "at every tide and high sea covered all with water, but when the sea ebbeth, and the tide is past, a man may pass over it as on dry land, but yet not without danger", as King John learned not without his loss (see below). Inspired by Camden's account, William Shakespeare mentioned the Lincolne-Washes in his stage play King John (1616). During the 17th and 18th centuries the name Wash came to be used for the estuary itself.

Drainage and reclamation works around the Wash continued until the 1970s. Large areas of salt marsh were progressively enclosed by banks and converted to agricultural land. The Wash is now surrounded by artificial sea defences on all three landward sides. In the 1970s, two large circular banks were built in the Terrington Marsh area of the Wash, as part of an abortive attempt to turn the entire estuary into a fresh water reservoir. The plan failed, not least because the banks were built using mud dredged from the salt marsh, which salinated fresh water stored there.

Hanseatic League
From 13th century the market town and seaport of Bishop's Lynn became the first member trading depot (Kontor) in the Kingdom of England of the Hanseatic League of ports. During the 14th century, Lynn ranked as the most important port in England, when sea trade with Europe was dominated by the League. It still retains two medieval Hanseatic League warehouses: Hanse House built in 1475 and Marriott's Warehouse.

King John and his jewellery
King John of England is said to have lost some of his jewels at the Wash in 1216. According to contemporary reports, John travelled from Spalding, Lincolnshire, to Bishop's Lynn, Norfolk, but was taken ill and decided to return. While he took the longer route by way of Wisbech, he sent his baggage train, comprising horse-drawn wagons, along the causeway and ford across the mouth of the Wellstream, a route usable only at low tide. The wagons moved too slowly to escape the incoming tide and many were lost. However, the treasure hunter and researcher Alan Marshall has proven from data supplied him by the Royal Greenwich Observatory and by the Bidston Observatory in Birkenhead that the tide had actually been going out, and by further studying the lay of the now reclaimed land, he ascertained that the cause had been a reverse tidal surge, whereby the outgoing tide suddenly sped up at a certain point. However, scholars cannot agree on whether the king's jewels were in the baggage train, and there is evidence that his regalia were intact after the journey. The accident was said to have occurred somewhere near Sutton Bridge on the River Nene.

John may have left his jewels in Lynn as security for a loan and arranged for their "loss". But that is considered an apocryphal account. He was recorded as staying the following night, 12–13 October 1216, at Swineshead Abbey, moving on to Newark-on-Trent, and dying of his illness on 19 October.

River and town names
The name of the river changed as a result of redirection of the Great Ouse in the 17th century.

Bishop's Lynn was renamed as King's Lynn in the 16th century as a result of King Henry VIII's establishment of the Church of England.

Air weapons training range
A Ministry of Defence weapons Range Danger Area lies along a small region of the Wash coastline, reserved for Royal Air Force, Army Air Corps and NATO-allied bombing and air weapons training. RAF Holbeach, active since 1926, was historically originally part of the former RAF Sutton Bridge station. Another air-weapons training range located on the Wash – RAF Wainfleet, operating from 1938, was decommissioned in 2010.

Local tradition
Sailing from out of the South Lincolnshire Fens into the Wash, especially for shell-fishing, is traditionally known locally as "going down below". The origin of the phrase is unclear.

Water channels etc
The bay is made up of multiple estuaries, marshland, deep water channels (in particular the Boston and Lynn Deeps), and shifting shallow water channels which are all surrounded by multiple sandbanks. Due to these features, it is claimed to be one of the most challenging and hazardous places for sea navigation in the world. It is fed by the rivers Witham, Welland, Nene and Great Ouse. It is a 620 km2 (240 sq. mi.) biological Site of Special Scientific Interest. It is also a Nature Conservation Review site, Grade I, a National Nature Reserve, a Ramsar site, a Special Area of Conservation and a Special Protection Area. It is in the Norfolk Coast Area of Outstanding Natural Beauty and part of it is the Snettisham Royal Society for the Protection of Birds nature reserve.

Landmarks
The four most distinctive man-made landmarks that can be seen from the bay are:

 * St Botolph's Church in Boston, the parish church of Boston. It has a tower known as the Boston Stump. This can be seen on clear days from the Norfolk side of the Wash particularly from Hunstanton. This dates from the 16th century and was often used by local fishermen as a navigation marker.
 * The Grain Storage Tower in King's Lynn docks.
 * Less prominently but particularly from the Norfolk side of the bay, Sutton Bridge Power Station
 * The former lighthouse at Old Hunstanton can also seen from parts of the bay on clear days particularly from Skegness and Gibraltar Point.

The Outer Trial Bank, a remnant of a 1970s experiment, lies some 2 mi off the Lincolnshire coast near the mouth of the River Nene.

The most notable nature feature is Hunstanton Cliffs, comprising strata of orange, red and white chalk.

Proposed racetrack
In 1934 a proposal was made, supported by racing driver Malcolm Campbell, to build a 15 mi race track on reclaimed land from Boston to Gibraltar Point, near Skegness. It would have been used as a road to Skegness when there was no racing. There was also to be a long lake for boat racing inside the track loop. The financial straits in the 1930s prevented the project from proceeding.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: The Wash


text:
Kenneth Clarke

Kenneth Harry Clarke, Baron Clarke of Nottingham, (born 2 July 1940) is a British politician who served as Home Secretary from 1992 to 1993 and Chancellor of the Exchequer from 1993 to 1997. A member of the Conservative Party, he was Member of Parliament (MP) for Rushcliffe from 1970 to 2019 and was Father of the House of Commons between 2017 and 2019. The President of the Tory Reform Group since 1997, he is a one-nation conservative who identifies with economically and socially liberal views.

Clarke served in the Cabinets of Margaret Thatcher and John Major as Chancellor of the Duchy of Lancaster from 1987 to 1988, Health Secretary from 1988 to 1990, and Education Secretary from 1990 to 1992. He held two of the Great Offices of State as Home Secretary and Chancellor of the Exchequer. He contested the Conservative Party leadership three times—in 1997, 2001 and 2005—being defeated each time. Opinion polls indicated he was more popular with the general public than with his party, whose generally Eurosceptic stance did not chime with his pro-European views. Under the coalition government of David Cameron, he returned to the Cabinet as Justice Secretary and Lord Chancellor from 2010 to 2012 and Minister without Portfolio from 2012 to 2014. He was also the United Kingdom Anti-Corruption Champion from 2010 to 2014.

The Conservative whip was withdrawn from him in September 2019 because he and 20 other MPs voted with the Opposition on a motion; for the remainder of his time in Parliament he sat as an independent, though still on the government benches. He stood down as an MP at the 2019 general election and was thereafter appointed by Boris Johnson as a Conservative Member of the House of Lords in September 2020.

Clarke is President of the Conservative Europe Group, Co-President of the pro-EU body British Influence and Vice-President of the European Movement UK. Described by the press as a 'Big Beast' of British politics, his total time as a minister is the fifth-longest in the modern era. He has spent over 20 years serving under Prime Ministers Edward Heath, Margaret Thatcher, John Major and David Cameron. He was one of only five ministers (Tony Newton, Malcolm Rifkind, Patrick Mayhew and Lynda Chalker are the others) to serve throughout the whole 18 years of the Thatcher–Major governments, which represents the longest uninterrupted ministerial service in Britain since Lord Palmerston in the early 19th century.

Early life and education
Clarke was born in West Bridgford, Nottinghamshire, and was christened with the same name as his father, Kenneth Clarke, a Nottinghamshire mining electrician and later a watchmaker and jeweller. He won a scholarship to attend the independent Nottingham High School before going to read for a law degree at Gonville and Caius College, Cambridge, where he graduated with an upper second honours degree. Clarke initially held Labour sympathies, and his grandfather was a Communist, but while at Cambridge he joined the Conservative Party.

As Chairman of the Cambridge University Conservative Association (CUCA), Clarke invited former British Fascist leader Sir Oswald Mosley to speak for two years in succession, prompting some Jewish students (including his future successor at the Home Office, Michael Howard) to resign from CUCA in protest. Howard then defeated Clarke in one election for the presidency of the Cambridge Union, but Clarke became President of the Cambridge Union a year later, being elected on 6 March 1963 by a majority of 56 votes. Clarke opposed the admission of women to the Union, and is quoted as saying upon his election, "The fact that Oxford has admitted them does not impress me at all. Cambridge should wait a year to see what happens before any decision is taken on admitting them."

In an early-1990s documentary, journalist Michael Cockerell played to Clarke some tape recordings of Clarke speaking at the Cambridge Union as a young man, and he displayed amusement at hearing his then-stereotypical upper class accent. Clarke is deemed one of the Cambridge Mafia, a group of prominent Conservative politicians who were educated at Cambridge in the 1960s. After leaving Cambridge, Clarke was called to the bar in 1963 at Gray's Inn, and was made Queen's Counsel in 1980.

Parliamentary career
Clarke sought election to the House of Commons almost immediately after leaving university. His political career began by contesting the Labour stronghold of Mansfield at the 1964 and 1966 elections. In June 1970, just before his 30th birthday, he won the East Midlands constituency of Rushcliffe in Nottinghamshire, south of Nottingham, from Labour MP Tony Gardner. From 2017 to 2019 he was Father of the House. Following his expulsion from the Conservative Party in September 2019, he became the first Independent MP to hold the position of Father of the House since Clement Tudway, who died in office as MP for Wells in 1815.

Clarke was soon appointed a Government whip, and served as such from 1972 to 1974; he, with the assistance of Labour rebels, helped ensure Edward Heath's government won key votes on British entry into the European Communities (which later evolved into the European Union). Even though Clarke opposed the election of Margaret Thatcher as Conservative Party Leader in 1975, he was appointed as her Industry Spokesman from 1976 to 1979, and then occupied a range of ministerial positions during her premiership.

Clarke is the subject of a portrait in oil commissioned by Parliament.

Early ministerial positions
Clarke first served in the government of Margaret Thatcher as Parliamentary Secretary for Transport (1979–81) and Parliamentary Under-Secretary of State for Transport (1981–82), and then Minister of State for Health (1982–85).

Clarke joined the Cabinet as Paymaster General and Employment Minister (1985–87) (his Secretary of State, Lord Young of Graffham, sat in the Lords), and served as Chancellor of the Duchy of Lancaster and Minister of the DTI (1987–88) with responsibility for Inner Cities. While in that position, Clarke announced the sale to British Aerospace of the Rover Group, a new name for British Leyland, which had been nationalised in 1975 by the Government of Harold Wilson.

Health Secretary
Clarke was appointed the first Secretary of State for Health when the department was created out of the former Department of Health and Social Security in July 1988. Clarke, with backing from John Major, persuaded Thatcher to accept the controversial "internal market" concept to the NHS. Clarke claimed that he had persuaded Thatcher to introduce internal competition in the NHS as an alternative to her preference for introducing a system of compulsory health insurance, which he opposed.

He told his biographer Malcolm Balen: "John Moore was pursuing a line which Margaret [Thatcher] was very keen on, which made everything compulsory medical insurance. I was bitterly opposed to that...The American system is...the world's worst health service – expensive, inadequate and with a lot of rich doctors". In her memoirs Thatcher claimed that Clarke, although "a firm believer in state provision", was "an extremely effective Health minister – tough in dealing with vested interests and trade unions, direct and persuasive in his exposition of government policy".

In January 1989, Clarke's White Paper Working for Patients appeared; this advocated giving hospitals the right to become self-governing NHS Trusts, taxpayer-funded but with control over their budgets and independent of the regional health authorities. It also proposed that doctors be given the option to become "GP fundholders". This would grant doctors control of their own budgets in the belief that they would purchase the most effective services for their patients. Instead of doctors automatically sending patients to the nearest hospital, they would be able to choose where they were treated. In this way, money would follow the patient and the most efficient hospitals would receive the greatest funding.

This was not well received by doctors and their trade union, the British Medical Association, launched a poster campaign against Clarke's reforms, claiming that the NHS was "underfunded, undermined and under threat". They also called the new GP contracts "Stalinist". A March 1990 opinion poll commissioned by the BMA showed that 73% believed that the NHS was not safe in Conservative hands. Clarke later claimed that the BMA was "the most unscrupulous trade union I have ever dealt with and I've dealt with every trade union across the board". Although Thatcher tried to halt the reforms just before they were introduced, Clarke successfully argued that they were necessary to demonstrate the government's commitment to the NHS. Thatcher told Clarke: "It is you I'm holding responsible if my NHS reforms don't work".

By 1994 almost all hospitals had opted to become trusts but GP fundholding was much less popular. There were allegations that fundholders received more funding than non-fundholders, creating a two-tier system. GP fundholding was abolished by Labour in 1997 and replaced by Primary Care Groups. According to John Campbell, by "the mid-1990s the NHS was treating more patients, more efficiently than in the 1980s...the system was arguably better managed and more accountable than before". Studies suggest that while the competition introduced in the "internal market" system resulted in shorter waiting times it also caused a reduction in the quality of care for patients.

Clarke has been the subject of criticism over the decades for his involvement in the contaminated blood scandal. It was the largest loss-of-life disaster in Britain since the 1950s and claimed the lives of thousands of haemophiliacs. Theresa May ordered a public inquiry into the contaminated blood scandal in July 2017. In July 2021, Clarke gave oral evidence to the inquiry with his demeanour being widely branded "arrogant, pompous and contemptuous" by the press. It was reported that he argued with inquiry counsel, refused to apologise and at one point even walked out while the chairman, Sir Brian Langstaff, was speaking.

The MSF trade union claimed that Clarke's exclusion of NHS medical laboratory staff from the pay review body in 1984 led to massive staff shortages and a crisis in medical laboratory testing by 1999.

Later ministerial positions
Just over two years later he was appointed Secretary of State for Education and Science in the final weeks of Thatcher's Government, following Norman Tebbit's unwillingness to return to Cabinet following the resignation of Sir Geoffrey Howe. Clarke was the first Cabinet Minister to advise Thatcher to resign after her victory in the first round of the November 1990 leadership contest was less than the 15% winning margin required to prevent a second ballot; she referred to him in her memoirs as a candid friend: "his manner was robust in the brutalist style he has cultivated: the candid friend".

Clarke came to work with John Major very closely, and quickly emerged as a central figure in his government. After continuing as Education Secretary (1990–92), where he introduced a number of reforms, he was appointed as Home Secretary in the wake of the Conservatives' victory at the 1992 general election. In May 1993, seven months after the impact of "Black Wednesday" had damaged Norman Lamont's credibility as Chancellor of the Exchequer, Major sacked Lamont and appointed Clarke in his place.

Chancellor of the Exchequer
At first, Clarke was seen as the dominant figure in Cabinet, and at the October 1993 Conservative Party Conference he defended Major from his critics by pronouncing "any enemy of John Major is an enemy of mine."

In the party leadership contest of 1995, when John Major beat John Redwood, Clarke kept faith in Major and commented: "I don't think the Conservative Party could win an election in 1,000 years on this ultra right-wing programme".

Clarke enjoyed an increasingly successful record as Chancellor, as the economy recovered from the recession of the early 1990s and a new monetary policy was put into effect after Black Wednesday. He reduced the basic rate of income tax from 25% to 23%, reduced UK Government spending as a percentage of GDP, and reduced the budget deficit from £50.8 billion in 1993 to £15.5 billion in 1997. Clarke's successor, the Labour Chancellor Gordon Brown, continued these policies, which eliminated the deficit by 1998 and allowed Brown to record a budget surplus for the following four years. Interest rates, inflation and unemployment all fell during Clarke's tenure at HM Treasury. Clarke's success was such that Brown felt he had to pledge to keep to Clarke's spending plans and these limits remained in place for the first two years of the Labour Government that was elected in 1997.

Single Currency: free hand and referendum pledge
The matter of a referendum on Britain joining the planned euro – first raised by Margaret Thatcher in 1990 – was, after much press speculation, raised again at Cabinet by Douglas Hogg in the spring of 1996, very likely (in Clarke's view) with Major's approval; Clarke records that Heseltine spoke "with passionate intensity" at Cabinet against a referendum, believing both that referendums were pernicious and that no concession would be enough to please the Eurosceptics. Clarke, who had already threatened resignation over the issue, also opposed the measure and, although Clarke and Heseltine were in a small minority in Cabinet, Major once again deferred a decision.

Major, Heseltine and Clarke eventually reached agreement in April 1996, in what Clarke describes as "a tense meeting ... rather like a treaty session", that there would be a commitment to a referendum before joining the euro, but that the pledge would be valid for one Parliament only (i.e. until the general election after next), with the Government's long-term options remaining completely open; Clarke threatened to resign if this formula were departed from.

Clarke, writing in 2016 after the Brexit Referendum, comments that he and Heseltine later agreed that they had separately decided to give way because of the pressure Major was under, and that the referendum pledge "was the biggest single mistake" of their careers, giving "legitimacy" to such a device.

In December 1996, after Foreign Secretary Malcolm Rifkind had commented that it was unlikely that the government would join the euro, Clarke and Heseltine took to the airwaves – in apparent unison – to insist that the government retained a free choice as to whether or not to join, angering Eurosceptics. When Tory Party Chairman, Brian Mawhinney, was understood to have briefed against him, Clarke declared: "tell your kids to get their scooters off my lawn" – an allusion to Harold Wilson's rebuke of Trades Union leader Hugh Scanlon in the late 1960s.

Role as a backbencher
After the Conservatives entered opposition in 1997, Clarke contested the leadership of the Party for the first time. In 1997, the electorate being solely Tory Members of Parliament, he topped the poll in the first and second rounds. In the third and final round he formed an alliance with Eurosceptic John Redwood, who would have become Shadow Chancellor and Clarke's deputy, were he to have won the contest. However, Thatcher endorsed Clarke's rival William Hague, who proceeded to win the election comfortably. The contest was criticised for not involving the rank-and-file members of the Party, where surveys showed Clarke to be more popular. Clarke rejected the offer from Hague of a Shadow Cabinet role, opting instead to return to the backbenches.

Clarke contested the party leadership for a second time in 2001. Despite opinion polls again showing he was the most popular Conservative politician with the British public, he lost in a final round among the rank-and-file membership, a new procedure introduced by Hague, to a much less experienced, but strongly Eurosceptic rival, Iain Duncan Smith. This loss, by a margin of 62% to 38%, was attributed to the former Chancellor's strong pro-European views being increasingly out-of-step with the party members' Euroscepticism. His campaign was managed by Andrew Tyrie.

Clarke opposed the 2003 invasion of Iraq. After choosing not to stand for the leadership after Duncan Smith departed in 2003 in the interests of party unity, he returned to fight the 2005 leadership election. He still retained huge popularity among voters, with 40% of the public believing he would be the best leader. He was accused by Norman Tebbit of being "lazy" whilst leadership rival Sir Malcolm Rifkind suggested that Clarke's pro-European views could have divided the Conservative Party had Clarke won. In the event, Clarke was eliminated in the first round of voting by Conservative MPs. Eventual winner David Cameron appointed Clarke to head a Democracy Task Force as part of his extensive 18-month policy review in December 2005, exploring issues such as the reform of the House of Lords and party funding. Clarke is President of the Tory Reform Group, a liberal, pro-European ginger group within the Conservative Party.

Clarke became known as "an economic and social liberal, an internationalist and a strong supporter of the European idea".

In 2006, he described Cameron's plans for a British Bill of Rights as "xenophobic and legal nonsense".

Expenses scandal
On 12 May 2009, The Daily Telegraph reported that Clarke had "flipped" his Council Tax. He had told the Parliamentary authorities that his main home was in the Rushcliffe constituency, enabling him to claim a second-home allowance on his London residence, leaving the taxpayer to foot the bill for Council Tax due on that property. However, he told Rushcliffe Borough Council in Nottinghamshire that he spent so little time at his constituency address that his wife Gillian should qualify for a 25% Council Tax (single person's) discount, saving the former Chancellor around £650 per year. Land Registry records showed that Clarke no longer had a mortgage on his Nottinghamshire home where he has lived since 1987. Instead he held a mortgage on his London property, which was being charged to the taxpayer at £480 per month.

Return to the frontbench
In 2009, Clarke became Shadow Business Secretary in opposition to the then-Business Secretary, Lord Mandelson. David Cameron described Clarke as about the only one able to challenge Mandelson and Brown's economic credibility. Two days later it was revealed that Clarke had warned in a speech a month earlier that President Barack Obama could see David Cameron as a "right-wing nationalist" if the Conservatives maintained Eurosceptic policies and that Obama would "start looking at whoever is in Germany or France if we start being isolationist". The Financial Times said "Clarke has in effect agreed to disagree with the Tories' official Eurosceptic line".

Lord Chancellor and Justice Secretary
On 12 May 2010, Clarke's appointment as Secretary of State for Justice and Lord Chancellor was announced by Prime Minister David Cameron in the Coalition Government formed between the Conservative and Liberal Democrat parties. James Macintyre, political editor of Prospect, argued that in this ministerial role he had instigated a process of radical reform.

In June 2010, Clarke signalled an end to short prison sentences after warning it was "virtually impossible" to rehabilitate any inmate in less than 12 months. In his first major speech after taking office, Clarke indicated a major shift in penal policy by saying prison was not effective in many cases. This could result in more offenders being handed community sentences. Clarke, who described the current prison population of 85,000 as "astonishing", received immediate criticism from some colleagues in a Party renowned for its tough stance on law and order. He signalled that fathers who fail to pay child maintenance, disqualified drivers and criminals fighting asylum refusals could be among the first to benefit and should not be sent to prison.

Clarke announced in February 2011 that the Government intended to scrutinise the relationship between the European Court of Human Rights and national parliaments.

In May 2011, controversy related to Clarke's reported views on sentencing for those convicted of rape resurfaced after an interview on the radio station BBC 5 Live, where he discussed a proposal to increase the reduction of sentences for criminals, including rapists, who pleaded guilty pre-trial, from a third to a half. In the interview he incorrectly asserted that the reason for the low average sentence of those convicted of rape was that legal definition of "rape" in England and Wales included such less serious offences as consensual sex between a 17 year old and a 15 year old.

In 2011 and 2012, Clarke faced criticism for his Justice and Security Bill, in particular those aspects of it that allow secret trials when "national security" is at stake. The Economist stated: "the origins of the proposed legislation lie in civil cases brought by former Guantánamo detainees, the best-known of whom was Binyam Mohamed, alleging that government intelligence and security agencies (MI6 and MI5) were complicit in their rendition and torture". Prominent civil liberties and human rights campaigners argued: "the worst excesses of the war on terror have been revealed by open courts and a free media. Yet the Justice and Security Green Paper seeks to place Government above the law and would undermine such crucial scrutiny."

Minister without Portfolio
Following the 2012 Cabinet reshuffle, Clarke was moved from Justice Secretary to Minister without Portfolio. It was also announced that he would assume the role of roving Trade Envoy with responsibility for promoting British business and trade interests abroad, a position which he enjoyed.

In the 2014 Cabinet reshuffle, after more than 20 years serving as a Minister, it was announced that Clarke had stepped down from government, to return to the backbenches. Clarke was honoured with appointment as a Member of the Order of the Companions of Honour, upon the Prime Minister's recommendation, in July 2014. His total time as a government minister is the fifth-longest in the modern era after Winston Churchill, Arthur Balfour, Rab Butler, and The Duke of Devonshire.

Return to the backbench
Clarke was opposed to Brexit during the 2016 referendum on the United Kingdom's continued membership of the European Union, and opposed the holding of the referendum in the first place. He was the sole Conservative MP to vote against the triggering of Article 50.

During the 2016 Conservative Party leadership election Clarke was interviewed by Sky News on 5 July 2016 and made negative comments to Sir Malcolm Rifkind, about the "fiasco" (leadership contest) and about three of the candidates. In a widely circulated video clip, he referred to Theresa May as a "bloody difficult woman", joked that Michael Gove, who was "wild", would "go to war with at least three countries at once" and characterised some of the utterances of Andrea Leadsom as "extremely stupid". Clarke added that Gove "did us all a favour by getting rid of Boris. The idea of Boris as prime minister is ridiculous."

In February 2017, following the death of Sir Gerald Kaufman, Clarke became Father of the House. He was re-elected as an MP in the 2017 general election.

In December 2017, he voted along with fellow Conservative Dominic Grieve and nine other Conservative MPs against the government, and in favour of guaranteeing Parliament a "meaningful vote" on any Brexit deal Britain agrees with the European Union.

Clarke endorsed Rory Stewart during the 2019 Conservative leadership election.

In September 2019, after Conservative Prime Minister Boris Johnson lost a number of key votes in the House of Commons, Clarke stated that it would be "not inconceivable" for him to become Prime Minister leading a government of national unity in order to revoke Article 50 and prevent Brexit. Other politicians who were suggested for such a role at the time included Harriet Harman, his female counterpart as Mother of the House of Commons. Lib Dem leader Jo Swinson supported the proposal, though Boris Johnson and Jeremy Corbyn, the Leader of the Opposition, both dismissed the suggestion. As it turned out, a vote of no-confidence was not in fact tabled against Boris Johnson's government and no such government of national unity was formed or took office.

Sitting as an Independent

On 3 September 2019, Clarke joined 20 other rebel Conservative MPs to vote against the Conservative government of Boris Johnson. The rebel MPs voted against a Conservative motion which subsequently failed. Effectively, they helped block Johnson's no-deal Brexit plan from proceeding on 31 October. Subsequently, all 21 were advised that they had lost the Conservative whip and were expelled as Conservative MPs, requiring them to sit as independents. If they decided to run for re-election in a future election, the party would block their selection as Conservative candidates, though Clarke opted not to do so.

On the edition of 3 September of BBC's Newsnight, Clarke discussed the situation, saying that he no longer recognised the Conservative Party, referring to it as "the Brexit Party, rebadged". His rationale was "It's been taken over by a rather knockabout sort of character, who's got this bizarre crash-it-through philosophy... a Cabinet which is the most right-wing Cabinet any Conservative Party has ever produced." In an interview on 7 September, Clarke rejected the suggestion that, like other former Conservative MPs, he could join the Liberal Democrats, but noted that, if he were to cast "a protest vote", he would "follow the Conservative tradition of voting Lib Dem."

In his capacity as Father of the House, Clarke presided over the House of Commons during the 2019 Speakership election. He then retired from the House of Commons at the 2019 general election. Since Dennis Skinner lost his seat in the election, Sir Peter Bottomley became Father of the House.

Peerage
In early 2020, Clarke was nominated for a peerage by Boris Johnson. On 4 September he was created Baron Clarke of Nottingham, of West Bridgford in the County of Nottinghamshire. Taking the Conservative whip, he made his maiden speech on 28 September 2020.

Corporate, media and other work
Whilst serving as a backbench MP and as a Shadow Cabinet Minister, Clarke accepted several non-executive directorships:

 * Deputy Chairman and a director of British American Tobacco (BAT) (1998–2007), for which Clarke faced allegations relating to activities of BAT in lobbying the developing world to reject stronger health warnings on cigarette packets and evidence the corporation had been involved in smuggling and targeting children with advertisements.
 * Deputy Chairman of Alliance Unichem
 * Chairman (non-executive) of Unichem
 * Director of Foreign & Colonial Investment Trust
 * Member from June 2007 of the Advisory Board of Centaurus Capital, a London-based hedge fund management company.
 * Clarke is a member of the advisory board of Agcapita Farmland Investment Partnership, a Canadian farmland investment fund.
 * Director (non-executive) of Independent News and Media (UK).
 * Participant at the annual meeting of the Bilderberg Group in 1993, 1998–2000, 2003–04, 2006–08 and 2012–13.

Also as a backbencher, Clarke declared engagement in non-political media work:
 * presented several series of jazz programmes on BBC Radio Four, including one on his namesake, bebop drummer Kenny Clarke
 * wrote a monthly column for Financial Mail on Sunday (£10,001–15,000)
 * wrote a weekly commentary or interview for Bloomberg Television (£10,001–15,000)
 * undertook occasional lecturing, on a self-employed basis.

Personal life
In 1964, Clarke married Gillian Edwards, a Cambridge contemporary. They had a son and a daughter. Edwards died of cancer in July 2015.

Clarke's enthusiasm for cigars, jazz and motor racing is well known, and he enjoys birdwatching as well as reading political history. He is also popularly recognised for his affection for suede Hush Puppies, a brand of shoe, which became a "trademark" of his during his early ministerial days. His autobiography denies he wore Hush Puppies and says these suede shoes were hand-made by Crockett & Jones.

Clarke is a sports enthusiast, being a supporter of both local football clubs Notts County and Nottingham Forest, who offered him a chair, and a former President of Nottinghamshire County Cricket Club. He is President of both Radcliffe Olympic and the Radcliffe on Trent Male Voice Choir, and a keen follower of Formula One motorsport. He was involved with tobacco giant British American Tobacco's Formula One team British American Racing (BAR) and has attended Grands Prix in support of the BAR team. BAR was sold to Honda in 2005. He also appeared on the podium of the 2012 British Grand Prix to present the first-place trophy to Mark Webber.

He attended the 1966 FIFA World Cup Final and jokingly claims to have been influential in persuading the linesman, Tofiq Bahramov, to award a goal to Geoff Hurst when the England striker had seen his shot hit the crossbar of opponents West Germany, leaving doubt as to whether the ball had crossed the line. Clarke's position in the Wembley crowd was right behind the linesman at the time and he shouted at the official to award a goal.

Clarke is a lover of real ale and has been an active member of the Campaign for Real Ale (CAMRA).

His memoir, Kind of Blue, was published in October 2016.

Honours

 * Made a Queen's Counsel (QC) in 1980.
 * Made an Honorary Bencher of Gray's Inn in 1989. Made a Full Bencher in 1997.
 * Sworn in as a Member of the Privy Council of the United Kingdom in 1985. This gave him the style "The Right Honourable".
 * Made a Member of the Order of the Companions of Honour (CH) in 2014.
 * Honorary degree of Doctor of Laws (LLD) from the University of Nottingham in 1989.
 * He was awarded an Honorary Fellowship by the Chartered Institute of Taxation in 2016.
 * Honorary degree of Doctor of the University (DUniv) from University of Derby in November 2017.
 * He was awarded an Honorary Fellowship by Gonville and Caius College, Cambridge.

title: Kenneth Clarke