Skip to content

Instantly share code, notes, and snippets.

@claytonjwong
Last active May 6, 2022 22:51
Show Gist options
  • Save claytonjwong/cb555fee87dca986c6d15f2fe0034714 to your computer and use it in GitHub Desktop.
Save claytonjwong/cb555fee87dca986c6d15f2fe0034714 to your computer and use it in GitHub Desktop.
template< typename T >
class Solution
{
using Vector = vector< T >;
using Iter = typename Vector::iterator;
Vector go( Vector&& A )
{
auto N{ A.size() };
if( N < 2 ) return A;
auto pivot{ A.cbegin() + N / 2 };
return merge( go({ A.cbegin(), pivot }), go({ pivot, A.cend() }) );
}
Vector merge( const Vector& lhs, const Vector& rhs, Vector res={} )
{
auto i{ lhs.cbegin() }, j{ rhs.cbegin() };
while( i < lhs.cend() && j < rhs.cend() ) res.push_back( ( *i < *j )? *i++ : *j++ );
if( i != lhs.cend() ) res.insert( res.end(), i, lhs.cend() );
if( j != rhs.cend() ) res.insert( res.end(), j, rhs.cend() );
return res;
}
public:
Vector mergeSort( const Vector& A )
{
return go({ A.cbegin(), A.cend() });
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment