Problem statement : Given a degree sequence D. Can we create a simple graph (graph without self loops and parallel edges) from D?

This is a classical problem that can be solved by using Havel-Hakimi algorithm or Erdős–Gallai theorem. Both of them have time complexity O(n^2). But I have found a task with N <= 100000 which is incompatible with O(n^2) algorithms. Is there any faster method to solve this?

(Edited) There are no any special conditions in this task

(Edited) Solved!! Optimize Erdős-Gallai Algorithm by using binary search to find min(di,k) of each k efficiently. New time complexity is O(n log n). Thanks 300iq and animeshf for this idea!

Link for Erdős-Gallai algorithm : https://en.wikipedia.org/wiki/Erdős–Gallai_theorem

Thanks everyone for replying.