ENH: Infer best datetime format from a sample
- [x] closes #52508 
- [x] [Tests added and passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#writing-tests) if fixing a bug or adding a new feature
- [x] All [code checks passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#pre-commit).
- [x] Added [type annotations](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#type-hints) to new arguments/methods/functions.
- [x] Added an entry in the latest `doc/source/whatsnew/v2.1.0.rst` file if fixing a bug or adding a new feature.

## Summary
``pd.to_datetime`` now tries to infer the datetime format of each string by considering
a random sample (instead of the first non-null sample),
and tries to find the format which work for most strings. If several
formats work as well, the one which matches the ``dayfirst`` parameter is returned. If
``format="mixed"``, pandas does the same thing, then tries the second best format on the
strings which failed to parse with the first best format, and so on (instead of parsing each row
independently) (#52508).

*Previous behavior*:

```
    In [1]: pd.to_datetime(["01-02-2012", "01-03-2012", "30-01-2012"])
    Out[1]:
    ValueError: time data "30-01-2012" doesn't match format "%m-%d-%Y", at position 2. You might want to try:
    - passing `format` if your strings have a consistent format;
    - passing `format='ISO8601'` if your strings are all ISO8601 but not necessarily in exactly the same format;
    - passing `format='mixed'`, and the format will be inferred for each element individually. You might want to use `dayfirst` alongside this.
    In [2]: pd.to_datetime(["01-02-2012", "01-03-2012", "30-01-2012"], errors="coerce")
    Out[2]:
    DatetimeIndex(['2012-01-02', '2012-01-03', 'NaT'], dtype='datetime64[ns]', freq=None)
    In [3]: pd.to_datetime(["01-02-2012", "01-03-2012", "30-01-2012"], format="mixed")
    Out[3]:
    DatetimeIndex(['2012-01-02', '2012-01-03', '2012-01-30'], dtype='datetime64[ns]', freq=None)
```
*New behavior*:

```
    In [1]: pd.to_datetime(["01-02-2012", "01-03-2012", "30-01-2012"])
    Out[1]:
    UserWarning: Parsing dates in %d-%m-%Y format when dayfirst=False was specified.
    Pass `dayfirst=True` or specify a format to silence this warning.
    DatetimeIndex(['2012-02-01', '2012-03-01', '2012-01-30'], dtype='datetime64[ns]',
    freq=None)
    In [2]: pd.to_datetime(["01-02-2012", "01-03-2012", "30-01-2012"], errors="coerce")
    Out[2]:
    UserWarning: Parsing dates in %d-%m-%Y format when dayfirst=False was specified. Pass `dayfirst=True` or specify a format to silence this warning.
    DatetimeIndex(['2012-02-01', '2012-03-01', '2012-01-30'], dtype='datetime64[ns]', freq=None)
    In [3]: pd.to_datetime(["01-02-2012", "01-03-2012", "30-01-2012"], format="mixed")
    Out[3]:
    DatetimeIndex(['2012-02-01', '2012-03-01', '2012-01-30'], dtype='datetime64[ns]', freq=None)
```

## Design questions:
- Do we bypass the `dayfirst` parameter too often? Right now, we always prefer the format which matches the most strings, and only consider `dayfirst` if several formats match as many strings (and raise a warning if we contradict `dayfirst`). For `error="raise"` it makes sense (we only select a format if it matches all non-null values), but I'm wondering if it's a problem for `errors="coerce"` or `errors="ignore"`: in this case, if `dayfirst = True` but `%m-%d%-%Y` matches more values than `%d-%m%-%Y`, we select `%m-%d%-%Y` (and raise a warning). I think it's okay but it may be somewhat confusing for users. Some ideas otherwise:
    - Have `dayfirst=None` (instead of `False`) as the default in `pd.to_datetime`, and respect `dayfirst` if it's provided.
    - Have some threshold of match percentage to be able to overwrite `dayfirst`: for instance  if `dayfirst = True`, `%m-%d%-%Y` needs to match >10% more values than `%d-%m%-%Y` to be chosen.
  


Thanks for the quick reply!
> * this looks very complicated, is a simpler solution possible?

Probably, I'll try to make it simpler.
> * this should be deterministic, and shouldn't depend on the result of `np.random` - can we use, say, the first 10 non-null elements? Or 10 equally spaced elements?

Will fix

 @MarcoGorelli this is ready for review (don't know if I should tag or just wait)
The failing build seems to be related to #52853, not related to the PR. Thanks for the reply!

> this still look quite complicated - this is going to have be maintained long-term by multiple people and so I'm a bit hesitant to add a lot of code. Is there a simpler solution which would still improve datetime format inference?

I understand the concern, but I'm not sure how to make it simpler. One thing I can easily remove, and is perhaps a bit complicated, is the `_iterative_conversion` part used when `format="mixed"`: maybe for now we could directly fall back to `dateutil` when `format="mixed"` is provided? This wouldn't fix the issue where pandas create two different date formats when one would work (e.g `pd.to_datetime(["01-02-2012", "13-01-2012"], format="mixed")` --> `DatetimeIndex(['2012-01-02', '2012-01-13'], dtype='datetime64[ns]', freq=None)`) but would make the code simpler.

 > maybe for now we could directly fall back to dateutil when format="mixed" is provided?

yeah `format='mixed'` means that no format inference should take place This pull request is stale because it has been open for thirty days with no activity. Please [update](https://pandas.pydata.org/pandas-docs/stable/development/contributing.html#updating-your-pull-request) and respond to this comment if you're still interested in working on this. Thanks for your PR

I'm afraid this introduces too much complexity, sorry, it's going to be too hard to maintain, there's already very few people comfortable with this part of the codebase 

If you can find a simpler solution which improves format inference without greatly increasing the maintenance burden, then we can take. For example, just trying 5 elements and taking a majority vote would probably be an improvement and still be quite simple